题解 | #乌龟棋#

/*dp[num1][num2][num3][num4]代表用了多少张各种卡片所能获得的最大利益*、
/*动态转移方程dp[num1][num2][num3][num4]=max{max(
dp[num1-1][num2][num3][num4]
dp[num1][num2-1][num3][num4]
dp[num1][num2][num3-1][num4]
dp[num1][num2][num3][num4-1]
)+map[1+num1+2*num2+3*num3+num4*4],dp[num1][num2][num3][num4]}
#include<iostream>
#include<algorithm>
using namespace std;
const int N=351,M=41;
int map[N],dp[M][M][M][M];
int main()
{
    int  n,m,a,b,c,d,number[5]={0};
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>map[i];
    for(int j=1;j<=m;j++)
    {
        int w;cin>>w;
        switch(w)
        {
            case 1 : number[1]++;break;
            case 2 : number[2]++;break;
            case 3 : number[3]++;break;
            case 4 : number[4]++;break;
        }
    }
    dp[0][0][0][0]=map[1];
    for(a=0;a<=number[1];a++)
     for(b=0;b<=number[2];b++)
      for(c=0;c<=number[3];c++)
       for(d=0;d<=number[4];d++)
       {
           int start=1;
           start+=a+b*2+c*3+d*4;
           if(a>=1)
           dp[a][b][c][d]=max(dp[a-1][b][c][d]+map[start],dp[a][b][c][d]);    
           if(b>=1)
           dp[a][b][c][d]=max(dp[a][b-1][c][d]+map[start],dp[a][b][c][d]);    
           if(c>=1)
           dp[a][b][c][d]=max(dp[a][b][c-1][d]+map[start],dp[a][b][c][d]);   
           if(d>=1)
           dp[a][b][c][d]=max(dp[a][b][c][d-1]+map[start],dp[a][b][c][d]);    
       }
    cout<<dp[number[1]][number[2]][number[3]][number[4]];
    return 0;
}