HDU 4939 Stupid Tower Defense

5517 단어 HDU
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
", ++kase , ans);
31 } 32 return 0; 33 }

좋은 웹페이지 즐겨찾기