首页 > 代码库 > HDU 4939 Stupid Tower Defense dp
HDU 4939 Stupid Tower Defense dp
因为瞬间伤害的塔一定是放在终点端的,所以枚举这种塔的个数
然后就能把n^3变成n^2了
#include <cstdio> #include <cstring> #include <algorithm> typedef long long ll; const int N = 1500 + 2; ll d[N][N]; // j = 3; int Tt = 0, n, x, y, z, t; inline void up(ll& a, ll v) { if (v > a) a = v; } void work() { ll ans = 0, T, D; scanf("%d%d%d%d%d", &n, &x, &y, &z, &t); for (int i = 0; i <= n; ++i) for (int j = 0; j <= i; ++j) d[i][j] = 0; for (int i = 0; i < n; ++i) for (int j = 0; j <= i; ++j) { T = t + (ll)z * j; D = T * (n - i) * x + T * (n - i) * y * (i - j) + d[i][j]; up(ans, D); // put a 2 up(d[i + 1][j], d[i][j] + (ll)(i - j) * y * T); up(d[i + 1][j + 1], d[i][j] + (ll)(i - j) * y * T); } for (int i = 0; i <= n; ++i) up(ans, d[n][i]); printf("Case #%d: %I64d\n", ++Tt, ans); } int main() { int cas; scanf("%d", &cas); while (cas -- > 0) work(); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。