HDU 4939 Stupid Tower Defense

 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 }