首页 > 代码库 > 2014多校第七场1005 || HDU 4939 Stupid Tower Defense （DP）

2014多校第七场1005 || HDU 4939 Stupid Tower Defense （DP）

2024-07-17 11:07:55   230人阅读

题目链接

题意 ：长度n单位，从头走到尾，经过每个单位长度需要花费t秒，有三种塔：

红塔 ：经过该塔所在单位时，每秒会受到x点伤害。

绿塔 ： 经过该塔所在单位之后的每个单位长度时每秒都会经受y点伤害。

蓝塔 ： 经过该塔所在单位之后，再走每个单位长度的时候时间会变成t+z。

思路 ： 官方题解 ：

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define LL long long 5  6 using namespace std ; 7  8 LL dp[1510][1510] ,n,x,y,z,t,ans; 9 10 int main()11 {12     int T ,casee = 1;13     scanf("%d",&T) ;14     while(T--)15     {16         memset(dp,0,sizeof(dp)) ;17         scanf("%I64d %I64d %I64d %I64d %I64d",&n,&x,&y,&z,&t) ;18         ans = n * t * x ;19         for(int i = 1 ; i <= n ; i ++)20         {21             for(int j = 0 ; j <= i ; j++ )22             {23                 if( !j ) dp[i][j] = dp[i-1][j] + t*(i-1-j) * y ;24                 else dp[i][j] = max(dp[i-1][j-1]+(i-j)*y*(t+(j-1)*z),dp[i-1][j]+(i-1-j)*y*(t+j*z)) ;25                 ans = max(ans,dp[i][j] + (n-i)*(j * z + t)*(x+(i-j)*y)) ;26             }27         }28         printf("Case #%d: %I64d\n",casee ++ ,ans) ;29     }30     return 0 ;31 }
View Code

 


联系
我们