hdu 4939 Stupid Tower Defense ( dp )

题目链接

题意：给出一条长为n个单位长度的直线，每通过一个单位长度需要t秒。

有3种塔，红塔可以在当前格子每秒造成x点伤害，绿塔可以在之后的格子每秒造成y点伤害，

蓝塔可以使通过单位长度的时间增加z秒。问如何安排3种塔的顺序使得造成的伤害最大，输出最大伤害值。

分析：比赛的时候实在是没有想出来有三种不同的 塔，每种塔的作用不同，怎么dp。看题解才知道，应该把

所有的红塔放到最后面，因为直线的长度是一定的，而红塔在前面不会增加后面的伤害，然后问题就是如何安排

绿塔和蓝塔，我这里d[i][j]代表前i个直线，放j个绿塔的最大值（貌似好多人喜欢写放蓝塔，不过是一样的）。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #define LL __int64

 const int maxn = +;

 using namespace std;

 LL d[maxn][maxn];

 int main()

 {

     int T, ca=;

     LL n, x, y, z, t, i, j;

     LL ans, ret;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%I64d%I64d%I64d%I64d%I64d", &n, &x, &y, &z, &t);

         ret = ;

         memset(d, , sizeof(d));

         ret = n*x*t; //刚开始少了全部都是红塔的情况，错了好多次，因为我下面写的是n-i;

         for(i = ; i <= n; i++)

         {

             for(j = ; j <= i; j++)

             {

                 LL tmp = ;

                 if(j!=i)

                 d[i][j] = d[i-][j]+y*j*(t+z*(i-j-)); //第i个放蓝塔

                 if(j!=)

                 tmp = d[i-][j-]+y*(j-)*(t+z*(i-j)); //第i个放绿塔

                 d[i][j] = max(tmp, d[i][j]);

                 ans = d[i][j]+(x+y*j)*(t+z*(i-j))*(n-i); //加上后面的伤害

                 if(ans > ret)

                 ret = ans;

             }

         }

         printf("Case #%d: %I64d\n", ca++, ret);

     }

     return ;

 }