题解:

每一步最多有4种选择,并且题目保证全部卡片用光后一定会正好走到终点,那么我们直接记忆化搜索就可以
dp[i][j][k][l] 表示 当前1,2,3,4卡片还剩i,j,k,l个得到的最大分数。时间复杂度为O(404040*40)

代码:

#include<bits/stdc++.h>
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> VI;
const int maxn = 1e6  + 4;

const int mod  = 1e8 + 7;
const int inf  = 0x3f3f3f3f;
const int N = 5005;
ll qpow(ll x,ll y){ll ans=1;x%=mod;assert(y>=0);while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}
//ctrl + h     ctrl + shift + t 
//ctrl + shift + d/k 
//alt  + shift + 1/2/3/4

int dp[41][41][41][41],w[maxn],ct[maxn],n,m,d;

int dfs(int a,int b,int c,int d,int i) {
    if(~dp[a][b][c][d]) return dp[a][b][c][d];

    int ans=0;
    if(a) ans=max(ans,dfs(a-1,b,c,d,i+1));
    if(b) ans=max(ans,dfs(a,b-1,c,d,i+2));
    if(c) ans=max(ans,dfs(a,b,c-1,d,i+3));
    if(d) ans=max(ans,dfs(a,b,c,d-1,i+4));
    return dp[a][b][c][d]=ans+w[i];
}

int main() {
    //freopen("E:\\S_Code\\input.in","r",stdin);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<=m;i++) scanf("%d",&d),ct[d]++;
    memset(dp,-1,sizeof dp);
    printf("%d\n",dfs(ct[1],ct[2],ct[3],ct[4],1));

    return 0;
}