首页 > 代码库 > Stupid Tower Defense
Stupid Tower Defense
题目链接
- 题意:
水平方向上n个1*1的格子,每个格子内部可以种一个植物,经过一个格子的时间为t。一共三种植物:R植物,经过时每秒收到r点伤害;G植物,经过后每秒受到g点伤害;B植物,经过后经过一个格子的时间加上b
2<=n<=1500,0<=r, g, b<=60000,1<=t<=3 - 分析:
最开始考虑的贪心:先B植物,后G植物,最后B植物,后来才发现是错误的。
首先明白,R植物对答案的影响和位置无关,而B和G植物越早种越好,所以问题就在于B和G的种法上。
状态表示要明白,不管G和B的位置如何,之后的情况只和B与G的数量有关,所以可以DP。DP[i][j]表示现在中了i个B植物,j个G植物的总伤害,可以贪心。实现采用一维DP处理
LL n, g, b, r, t; LL dp[MAXN]; int main() { int T; RI(T); FE(kase, 1, T) { cin >> n >> r >> g >> b >> t; LL ans = n * r * t; CLR(dp, -1); dp[0] = 0; REP(all, n) { FED(i, n, 0) { if (~dp[i]) { LL nxt = dp[i] + (i * b + t) * (all - i) * g; if (dp[i + 1] < nxt) dp[i + 1] = nxt; nxt = dp[i] + (i * b + t) * (all - i) * g; if (dp[i] < nxt) dp[i] = nxt; } } FE(i, 0, n) { if (~dp[i]) { LL nxt = dp[i] + (n - all - 1) * (t + i * b) * (r + (all + 1 - i) * g); if (ans < nxt) ans = nxt; } } } printf("Case #%d: %I64d\n", kase, ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。