题意：

有一条由\(n\)块瓷砖组成的路，每个瓷砖都有一个权值\(a_i\)。现在有个乌龟，有\(m\)张\(4\)种的卡片，分别是\(1,2,3,4\)。每张卡牌上的数字代表他能够向前走多少步。现在问题，这个乌龟用这\(m\)种卡片走到终点最多可以获取多少积分。

分析:

因为最终的结果跟每次选取卡牌的状态有关，故不妨设一个最暴力的\(dp\)式子：\(dp[a][b][c][d][pos]\)代表现在有\(a\)张\(1\)卡牌，\(b\)张\(2\)卡牌，\(c\)张\(3\)卡牌，\(d\)张\(4\)卡牌，且当前的位置为\(pos\)。显然当前的位置可以从四个部分转移而来，因此有转移方程\[dp[a][b][c][d][pos]=max(dp[a-1][b][c][d][pos_1],dp[a][b-1][c][d][pos_2],dp[a][b][c-1][d][pos_3],dp[a][b][c][d-1][pos_4])+a[pos]\]。而显然当前的\(pos\)可以通过\(a,b,c,d\)计算得出，因此我们只需要开一个四维的状态记录即可。时间复杂度\(\mathcal{O}(n^4)\)

代码：

#include 
    
     #define maxn 355using namespace std;int dp[50][50][50][50];int a[maxn],mp[5];int main(){    int n,m;    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);    }    while(m--){        int num;        scanf("%d",&num);        mp[num]++;    }    dp[0][0][0][0]=a[1];    for(int i=0;i<=mp[1];i++){        for(int j=0;j<=mp[2];j++){            for(int k=0;k<=mp[3];k++){                for(int kk=0;kk<=mp[4];kk++){                    int cur=(i+j*2+k*3+kk*4+1);                    if(i!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i-1][j][k][kk]+a[cur]);                    if(j!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i][j-1][k][kk]+a[cur]);                    if(k!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i][j][k-1][kk]+a[cur]);                    if(kk!=0) dp[i][j][k][kk]=max(dp[i][j][k][kk],dp[i][j][k][kk-1]+a[cur]);                }            }        }    }    printf("%d\n",dp[mp[1]][mp[2]][mp[3]][mp[4]]);    return 0;}