题解 P1541 【乌龟棋】

其实这道题想到了就很简单，但很难想到用四维的dp，这非常少见。 看到每张牌不超过40张，这数据范围就是给你开四维dp的 自然想到用dp[ i ][ j ][ k ][ l ]表示用了i张1，j张2，k张3 , l 张4的最大值 用i张1，j张2，k张3 , l 张4自然跳到了 第（1+i+2\*j+3\*k+4\*l）格，枚举四种情况，再加上第（1+i+2\*j+3\*k+4\*l）格的值就行了 转移方程见代码，打起来太烦了……………… ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; int a[351]; int c[5]={0}; int dp[41][41][41][41]={0}; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { int x; scanf("%d",&x); c[x]++; //统计每张牌的数量 } for(int i=0;i<=c[1];i++) for(int j=0;j<=c[2];j++) for(int k=0;k<=c[3];k++) for(int l=0;l<=c[4];l++) //枚举 dp[i][j][k][l]=max(max(max(dp[max(0,i-1)][j][k][l],dp[i][max(0,j-1)][k][l]),dp[i][j][max(0,k-1)][l]),dp[i][j][k][max(0,l-1)])+a[1+i+2*j+3*k+4*l]; //四种情况的转移方程。怀疑是史上最长………… printf("%d",dp[c[1]][c[2]][c[3]][c[4]]); //用完牌就到达了终点，输出即可 return 0; } ```