洛谷 P1541 乌龟棋（DP）
题目链接：https://www.luogu.com.cn/problem/P1541
设dp[i][j][k][q]，表示1用了i个，2用了j个，3用了k个，4用了q个。那么此时的pos可以表示出来，每次取max。
AC代码
递推：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int N=400; 6 const int M=50; 7 int n,m; 8 int a[N],b[N]; 9 int dp[M][M][M][M]; 10 int main(){ 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 13 for(int i=1;i<=m;i++) { int x; scanf("%d",&x); b[x]++;} 14 dp[0][0][0][0]=a[1]; 15 for(int i=0;i<=b[1];i++) 16 for(int j=0;j<=b[2];j++) 17 for(int k=0;k<=b[3];k++) 18 for(int q=0;q<=b[4];q++){ 19 int pos=1+i+j*2+k*3+q*4; 20 if(i) dp[i][j][k][q]=max(dp[i][j][k][q],dp[i-1][j][k][q]+a[pos]); 21 if(j) dp[i][j][k][q]=max(dp[i][j][k][q],dp[i][j-1][k][q]+a[pos]); 22 if(k) dp[i][j][k][q]=max(dp[i][j][k][q],dp[i][j][k-1][q]+a[pos]); 23 if(q) dp[i][j][k][q]=max(dp[i][j][k][q],dp[i][j][k][q-1]+a[pos]); 24 } 25 printf("%d",dp[b[1]][b[2]][b[3]][b[4]]); 26 return 0; 27 }
记忆化：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int N=400; 6 const int M=50; 7 int n,m; 8 int dp[M][M][M][M]; 9 int a[N],b[N]; 10 int DFS(int i,int j,int k,int q){ 11 if(dp[i][j][k][q]) return dp[i][j][k][q]; 12 if(i==b[1]&&j==b[2]&&k==b[3]&&q==b[4]) return 0; 13 int pos=1+i+j*2+k*3+q*4; 14 int ans=0; 15 if(i<b[1]) ans=max(ans,DFS(i+1,j,k,q)+a[pos+1]); 16 if(j<b[2]) ans=max(ans,DFS(i,j+1,k,q)+a[pos+2]); 17 if(k<b[3]) ans=max(ans,DFS(i,j,k+1,q)+a[pos+3]); 18 if(q<b[4]) ans=max(ans,DFS(i,j,k,q+1)+a[pos+4]); 19 return dp[i][j][k][q]=ans; 20 } 21 22 int main(){ 23 scanf("%d%d",&n,&m); 24 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 25 for(int j=1;j<=m;j++) { int x; scanf("%d",&x); b[x]++;} 26 printf("%d",DFS(0,0,0,0)+a[1]); 27 return 0; 28 }