乌龟棋

题意：

给你个格子上的数字，张卡片，卡片分为种（分别走步），让你找出一种使用卡牌的顺序让得分最大。

分析：

既然有个格子，我们不妨定义

从第个格子到第个格子最大的得分数

但是我们并不知道当前到第个格子的卡牌使用情况，而一共有种卡牌，所以状态可以变成

从第1个格子到第个格子使用张1步牌，张2步牌，张3步牌，张4步牌的最大得分数。

又因为已知牌的使用情况，必定能得出唯一当前处在的格子，所以能将状态再优化

从第1个格子到第格子使用张1步牌，张2步牌，张3步牌，张4步牌的最大得分数。

即可得到转移方程为

#include<bits/stdc++.h>
using namespace std;
int n,m,arr[355],cnt[5];
int f[45][45][45][45];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        cnt[x]++;
    }
    f[0][0][0][0]=arr[1];
    for(int a=0;a<=cnt[1];a++)
        for(int b=0;b<=cnt[2];b++)
            for(int c=0;c<=cnt[3];c++)
                for(int d=0;d<=cnt[4];d++){
                    if(a!=0)
                        f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+arr[1+a+2*b+3*c+4*d]);
                    if(b!=0)
                        f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+arr[1+a+2*b+3*c+4*d]);
                    if(c!=0)
                        f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+arr[1+a+2*b+3*c+4*d]);
                    if(d!=0)
                        f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+arr[1+a+2*b+3*c+4*d]);
                }
    printf("%d",f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
    return 0;
}