首页 > 代码库 > 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与煎饼
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。