记忆化搜索

#include<bits/stdc++.h>
using namespace std;
int n,m,scores[355],cnt[5]={0};
int dp[45][45][45][45];
int dfs(int pos,int used1,int used2,int used3,int used4){
    if(pos==n)
        return 0;
    if(dp[used1][used2][used3][used4]!=-1)
        return dp[used1][used2][used3][used4];
    int maxs=0;
    if(used1<cnt[1]&&pos+1<=n){
        int npos=pos+1,cur=scores[npos-1];
        maxs=max(maxs,cur+dfs(npos,used1+1,used2,used3,used4));
    }
    if(used2<cnt[2]&&pos+2<=n){
        int npos=pos+2,cur=scores[npos-1];
        maxs=max(maxs,cur+dfs(npos,used1,used2+1,used3,used4));
    }
    if(used3<cnt[3]&&pos+3<=n){
        int npos=pos+3,cur=scores[npos-1];
        maxs=max(maxs,cur+dfs(npos,used1,used2,used3+1,used4));
    }
    if(used4<cnt[4]&&pos+4<=n){
        int npos=pos+4,cur=scores[npos-1];
        maxs=max(maxs,cur+dfs(npos,used1,used2,used3,used4+1));
    }
    return dp[used1][used2][used3][used4]=maxs;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>scores[i];
    for(int i=1;i<=m;i++){
        int c;
        cin>>c;
        cnt[c]++;
    }
    memset(dp,-1,sizeof(dp));
    cout<<scores[0]+dfs(1,0,0,0,0);
    return 0;
}