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

HDU 4939 Stupid Tower Defense

2024-07-18 08:15:56   215人阅读

dp；枚举red，dp前i 个塔中有j 个蓝塔的最大伤害。

机智的地方：dp前i 个塔的时候可以同时处理n-i 个红塔，这样就少了个循环。。。（枚举红塔的循环）

 

 

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

 


联系
我们