首页 > 代码库 > TaoSama与煎饼

TaoSama与煎饼

技术分享

技术分享

 

1.这DP写得想哭~~~

2.好不容易想出dp[i][j][k][l]的状态,却把遍历的顺序写反了(我写的是从后向前,那么t[1],t[2],t[3],t[4]中某项为0时,就崩溃了),导致越写越复杂。

3.orzzzzzzzzz

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 int T,n,m;
 8 int dp[45][45][45][45],c[400],t[5];
 9 
10 int main()
11 {    scanf("%d",&T);
12      while(T--){
13         scanf("%d%d",&n,&m);
14         memset(c,0,sizeof(c));
15         memset(t,0,sizeof(t));
16         memset(dp,0,sizeof(dp));
17         for(int i=1;i<=n;i++) scanf("%d",&c[i]);
18         for(int i=1;i<=m;i++){
19             int tem;scanf("%d",&tem);
20             t[tem]++;
21         }
22         dp[0][0][0][0]=c[1];
23         for(int i=0;i<=t[1];i++){
24             for(int j=0;j<=t[2];j++){
25                 for(int k=0;k<=t[3];k++){
26                     for(int l=0;l<=t[4];l++){
27                         if(i) dp[i][j][k][l]=max(dp[i][j][k][l],c[1+i+j*2+k*3+l*4]+dp[i-1][j][k][l]);
28                         if(j) dp[i][j][k][l]=max(dp[i][j][k][l],c[1+i+j*2+k*3+l*4]+dp[i][j-1][k][l]);
29                         if(k) dp[i][j][k][l]=max(dp[i][j][k][l],c[1+i+j*2+k*3+l*4]+dp[i][j][k-1][l]);
30                         if(l) dp[i][j][k][l]=max(dp[i][j][k][l],c[1+i+j*2+k*3+l*4]+dp[i][j][k][l-1]);
31                     }
32                 }
33             }
34         }
35         printf("%d\n",dp[t[1]][t[2]][t[3]][t[4]]);
36     }
37 } 

 

TaoSama与煎饼