https://www.luogu.org/problemnew/show/P1541

题解：

1.F[a][b][c][d]:表示你出了a张爬行牌1，b张爬行牌2，c张爬行牌3，d张爬行牌4时的得分

2.g[x]:表示牌x一共有多少张

题干中说如何出牌,那我们就不妨DP一下每一种牌的出牌张数

初始化：

F[0][0][0][0]=num[1];

显然,乌龟开始时在num[1],题中说乌龟棋子自动获得起点格子的分数,故未出牌时（F[0][0][0][0]）分数为num[1]

之后边输入边存每一种牌的张数（输入数据第3行:M个整数，b1b2……bM，表示M张爬行卡片上的数字,故卡1~卡4张数一定）:

for(int i=1;i<=m;i++)
{
    cin>>x;
    g[x]++;
}

之后便可以开始DP了:

起始状态F[0][0][0][0]=num[1]，即不出任何爬行卡;之后对于每一张卡片，我都可以选择放与不放， E:设当前放的卡1数量为a，卡2数量为b，卡3数量为c，卡4数量为d（以下出现a~d均为这个意思），则对于卡一:

比较卡一的放与不放,只需决策卡一的放与不放，即取F[a][b][c][d],F[a-1][b][c][d]+num[r]的最大值。又由于a有一定数量,所以我们可以得出关于a的转移方程:

    F[a][b][c][d]=max(F[a][b][c][d],F[a-1][b][c][d]+num[r])

其中r=1+a+b2+c3+d4(至于r在a+b2+c3+d4加一原因见后)

DP 数量a：

for(int a=0;a<=g[1];a++)
{
    int r=1+a+b*2+c*3+d*4;
    if(a!=0)    F[a][b][c][d]=max(F[a][b][c][d],F[a-1][b][c][d]+num[a+b*2+c*3+d*4])
}

这不就是个“物品占的空间”为1，“价值”为num[r]的多重背包嘛！！

至于这个(a!=0)，显然，你要是调用F[a-1][b][c][d]，肯定得保证a-1>=0吧。a显然作为卡1个数不可能<0,故取(a!=0)即可

根据多维背包的思想，背包DP几个“价值”（即爬行牌种类）开几维即可,故 转移方程为:

        F[a][b][c][d]=max(F[a-1][b][c][d],F[a][b-1][c][d],F[a][b][c-1][d],F[a][b][c][d-1])+num[1*a+2*b+3*c+4*d]

最后DP出来的F[g[1]][g[2]][g[3]][g[4]]即为答案。

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=10000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,q;
int a[N],b[5];
int dp[50][50][50][50];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&t);
        b[t]++;
    }
    dp[0][0][0][0]=a[1];
    for(int i=0;i<=b[1];i++){
        for(int j=0;j<=b[2];j++){
            for(int k=0;k<=b[3];k++){
                for(int l=0;l<=b[4];l++){
                    q=1+i*1+j*2+k*3+l*4;
                    if(i)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l]+a[q]);
                    if(j)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k][l]+a[q]);
                    if(k)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l]+a[q]);
                    if(l)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l-1]+a[q]);
                }
            }
        }
    }
    cout<<dp[b[1]][b[2]][b[3]][b[4]]<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}