首页 > 代码库 > HDU 4939 Stupid Tower Defense(贪心+dp)
HDU 4939 Stupid Tower Defense(贪心+dp)
HDU Stupid Tower Defense
题目链接
题意:有一些塔,红塔能攻击经过他的,绿塔能攻击经过之后的,蓝塔能把经过之后的减速,求在1-n上放塔,求伤害最大值
思路:一开始以为直接贪心,绿塔最前,蓝塔中间,红塔最后就可以了,结果其实是错的
不过,红塔放最后是肯定的,这个很显然就不多证明了,是贪心的思想
然后就dp[i][j]表示放到i,前面有j个绿塔去状态转移即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1505; typedef long long ll; int T; ll n, x, y, z, t; ll dp[N][N]; ll solve() { ll ans = n * x * t; dp[0][0] = 0; for (ll i = 1; i <= n; i++) { for (ll j = 0; j <= i; j++) { dp[i][j] = 0; if (j != i) dp[i][j] = max(dp[i][j], dp[i - 1][j] + y * j * (t + (i - j - 1) * z)); if (j) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + y * (j - 1) * (t + (i - j) * z)); ans = max(ans, dp[i][j] + (t + (i - j) * z) * (n - i) * (x + y * j)); } } return ans; } int main() { int cas = 0; scanf("%d", &T); while (T--) { scanf("%I64d%I64d%I64d%I64d%I64d", &n, &x, &y, &z, &t); printf("Case #%d: %I64d\n", ++cas, solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。