首页 > 代码库 > HDU 4939 Stupid Tower Defense(dp)
HDU 4939 Stupid Tower Defense(dp)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4939
解题报告:一条长度为n的线路,路上的每个单元格可以部署三种塔来给走在这条路上的敌人造成伤害,第一种塔只给在这个塔的范围内的敌人每秒造成x点的伤害,第二种塔给已经经过过这个塔的敌人每秒造成y点伤害,第三种塔能使已经经过了这个塔的敌人的前进的速度减慢,具体效果是,原来敌人经过一个单元格的时间是t秒,经过减速后,经过每个单元格的时间是t + z,这个一个塔减速的效果,减速的效果可以叠加,同样,第二种塔的伤害的效果也可以叠加,每个单元格只能放一个塔。
dp[i][j]表示的是前i个放的是绿塔或蓝塔,到第i个单元格的最大伤害,然后递推公式是:
dp[i][j] = max(dp[i-1][j] + (i-j-1)*(j*z+t)*y ,dp[i-1][j-1] +(i-j)*((j-1)*z+t)*y);
最后加上后面n-i个的伤害,后面n-i个就是全部放第一种塔了。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 #define LL __int64 7 LL dp[2005][2000]; 8 9 LL n,x,y,z,t;10 11 int main()12 {13 int T,kase = 1;14 scanf("%d",&T);15 while(T--)16 {17 scanf("%I64d%I64d%I64d%I64d%I64d",&n,&x,&y,&z,&t);18 memset(dp,0,sizeof(dp));19 LL ans = n * x * t;20 for (int i = 1; i <= n; ++i)21 {22 dp[i][0] = dp[i-1][0] + t * (i - 1) * y;23 ans=max(ans,dp[i][0] + t*y*(n - i)*i + x*(n - i)*t);24 }25 for(int i = 1;i <= n;++i)26 for(int j = 1;j <= i;++j)27 if(i == j) dp[i][j] = 0;28 else dp[i][j] = max(dp[i-1][j] + (i-1-j)*y*(j*z+t),dp[i-1][j-1] + y * (i - j) * ((j-1) * z + t));29 for(int i = 1;i <= n;++i)30 for(int j = 1;j <= i;++j)31 {32 dp[i][j] += ((n-i)*x*(j * z + t) + (n-i)*(i-j)*(j*z+t)*y);33 ans = dp[i][j] > ans? dp[i][j]:ans;34 }35 printf("Case #%d: %I64d\n",kase++,ans);36 }37 return 0;38 }39 /*40 1041 4 1 1 1 142 Case #1: 943 1 3 10 3 144 Case #2: 045 3 1 10 1 346 Case #3: 7447 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。