例子当然是王八棋这道题，这道题以前是写烂了
先来一个大暴力，zlw教的暴力~~
1 #include<iostream> 2 using namespace std; 3 const int maxn=355,maxm=125; 4 int a[maxn],b[5]; 5 int n,m; 6 int ans=0; 7 int MAX(int x,int y) 8 { 9 return x>y?x:y; 10 } 11 void dfs(int dp,int pos,int tmp) 12 { 13 ans=MAX(ans,tmp); 14 for(int i=1;i<=4;i++) 15 if(b[i]) 16 { 17 b[i]--; 18 dfs(dp+1,pos+i,tmp+a[pos+i]); 19 b[i]++; 20 } 21 } 22 int main() 23 { 24 cin>>n>>m; 25 for(int i=1;i<=n;i++) 26 cin>>a[i]; 27 for(int i=1;i<=m;i++) 28 { 29 int x; 30 cin>>x; 31 if(x==1) b[1]++; 32 if(x==2) b[2]++; 33 if(x==3) b[3]++; 34 if(x==4) b[4]++; 35 } 36 dfs(1,1,a[1]); 37 cout<<ans<<endl; 38 return 0; 39 }
当时真是幼稚地连搜索都写不利索
多维动态规划的意思就是状态有好几个维度，我们在定义状态的时候要开多维数组
这道题里面四种卡牌用了多少了是四种可行的状态，还有一个是当前走到了哪个格子，作为阶段
f[][][][][]，然后就是这样了，MLE
这道题的思路是把阶段这一维度压掉，因为其可以用其他的状态来表示
一般的想法是把别的状态压掉，其实同样也能A掉这道题
压掉状态还是自然一些，压掉阶段就不太自然了
即使看上去很自然的样子
总的来说，好题一道，出题人无敌
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int INF=0x7f7f7f7f; 6 const int maxn=355,maxm=125; 7 int n,m,a,b,c,d,ans; 8 int t[maxn]; 9 int f[44][44][44][44]; 10 int main() 11 { 12 13 scanf("%d%d",&n,&m); 14 for(int i=1;i<=n;i++) scanf("%d",&t[i]); 15 int x; 16 for(int i=1;i<=m;i++) 17 { 18 scanf("%d",&x); 19 if(x==1) a++; 20 if(x==2) b++; 21 if(x==3) c++; 22 if(x==4) d++; 23 } 24 for(int i=0;i<=a;i++) 25 for(int j=0;j<=b;j++) 26 for(int k=0;k<=c;k++) 27 for(int l=0;l<=d;l++) 28 { 29 if(i!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]); 30 if(j!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]); 31 if(k!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]); 32 if(l!=0) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]); 33 f[i][j][k][l]+=t[i+2*j+k*3+l*4+1]; 34 } 35 printf("%d",f[a][b][c][d]); 36 return 0; 37 }
这是一个5D/0D压成了4D/0D的动态规划？