首页 > 代码库 > hdu 4939 Stupid Tower Defense ( dp )
hdu 4939 Stupid Tower Defense ( dp )
题目链接
题意:给出一条长为n个单位长度的直线,每通过一个单位长度需要t秒。
有3种塔,红塔可以在当前格子每秒造成x点伤害,绿塔可以在之后的格子每秒造成y点伤害,
蓝塔可以使通过单位长度的时间增加z秒。问如何安排3种塔的顺序使得造成的伤害最大,输出最大伤害值。
分析:比赛的时候实在是没有想出来有三种不同的 塔,每种塔的作用不同,怎么dp。看题解才知道,应该把
所有的红塔放到最后面,因为直线的长度是一定的,而红塔在前面不会增加后面的伤害,然后问题就是如何安排
绿塔和蓝塔,我这里d[i][j]代表前i个直线,放j个绿塔的最大值(貌似好多人喜欢写放蓝塔,不过是一样的)。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #define LL __int64 7 const int maxn = 1500+10; 8 using namespace std; 9 LL d[maxn][maxn];10 11 int main()12 {13 int T, ca=1;14 LL n, x, y, z, t, i, j;15 LL ans, ret;16 scanf("%d", &T);17 while(T--)18 {19 scanf("%I64d%I64d%I64d%I64d%I64d", &n, &x, &y, &z, &t);20 ret = 0;21 memset(d, 0, sizeof(d));22 ret = n*x*t; //刚开始少了全部都是红塔的情况,错了好多次,因为我下面写的是n-i;23 for(i = 1; i <= n; i++)24 {25 for(j = 0; j <= i; j++)26 {27 LL tmp = 0;28 if(j!=i)29 d[i][j] = d[i-1][j]+y*j*(t+z*(i-j-1)); //第i个放蓝塔30 if(j!=0)31 tmp = d[i-1][j-1]+y*(j-1)*(t+z*(i-j)); //第i个放绿塔32 33 d[i][j] = max(tmp, d[i][j]);34 ans = d[i][j]+(x+y*j)*(t+z*(i-j))*(n-i); //加上后面的伤害35 if(ans > ret)36 ret = ans;37 }38 }39 printf("Case #%d: %I64d\n", ca++, ret);40 }41 return 0;42 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。