首页 > 代码库 > HDU 4939 Stupid Tower Defense dp

HDU 4939 Stupid Tower Defense dp

2024-07-17 05:31:52   225人阅读

题意：给你一段长为n的路，每一个单位长度可以放一种塔，这里有三种塔。

1）对正在经过这座塔的敌人进行 x 每秒伤害的攻击

2）对于已经经过这塔的敌人进行y每秒的伤害攻击

3）对已经经过这个塔的敌人放慢速度，使得原先为 经过一个单位时间为  t的速度变为  t+k

解题思路：我们可以知道，第一种塔一定是放在最后面的，然后进行DP，DP[i][j] 代表经过了 i  座塔其中有  j 座是第二种塔的最大值（其余的是第三种塔），对每一个dp[i][j]计算总时间就行。

状态转移方程为  dp[i][j] = max(dp[i-1][j-1] + y*(j-1)*(t+(i-j)*k) , dp[i-1][j] + y*j*(t +(i-j-1)*k))

但是在考虑状态的时候要特别注意对于j == i 的情况 ，这种情况是没有 dp[i-1][j]的 比赛的时候竟是因为这里没有考虑导致了一直找不出bug，所以这里还是需要把问题都考虑全面。

解题代码：

 1 // File Name: 1005.cpp 2 // Author: darzdream 3 // Created Time: 2014年08月12日 星期二 12时25分19秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<bitset>11 #include<algorithm>12 #include<functional>13 #include<numeric>14 #include<utility>15 #include<sstream>16 #include<iostream>17 #include<iomanip>18 #include<cstdio>19 #include<cmath>20 #include<cstdlib>21 #include<cstring>22 #include<ctime>23 #define LL long long24 25 using namespace std;26 LL n ,x , y , z , t ;27 LL ans = 0 ; 28 LL dp[1600][1602];// 前I 个塔选多少个y塔。29 void solve()30 {31      for(int i = 0;i <= n ;i ++ )32          for(int j =0 ;j <= n;j ++)33          {34             dp[i][j] = 0; 35          }36      ans = x*n*t;37      for(int i = 1 ;i <= n;i ++)38      {39        for(int j = 0;j <= i ;j ++)40         {41             if(j >= 1)42             {43                 dp[i][j] = max(dp[i-1][j-1] + y*(j-1)*(t+(i-j)*z), dp[i-1][j] + y*j*(t+(i-1-j)*z)); // maybe wa44                 if(i == j )45                 {46                    dp[i][j] = dp[i-1][j-1] + y*(j-1)*(t+(i-j)*z); // maybe wa47                 }48             }49             if(dp[i][j] + (x + j* y)*(t+(i-j)*z)*(n-i)  > ans)50             {51               ans = dp[i][j] + (x + j * y)*(t+(i-j)*z)*(n-i) ;52             }53         }54      }55 }56 int main(){57    int T;58   //freopen("input","r",stdin);59    //freopen("output1","w",stdout);60    scanf("%d",&T);61    for(int ca = 1; ca <= T ;ca ++)62    {63       scanf("%I64d %I64d %I64d %I64d %I64d",&n,&x,&y,&z,&t);64       solve(); 65       printf("Case #%d: %I64d\n",ca,ans);66    }67 return 0;68 }
View Code

 


联系
我们