算法

线性dp

$f[i][j][k][l]$表示用了i张1，j张2，k张3，l张4的获得的最大花费。

时间复杂度

$O(40^4)$

C++ 代码

#include <iostream>
using namespace std;
int n,m;
int a[400],b[5];
int f[41][41][41][41];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=1;i<=m;++i) {
        int x;
        cin>>x;
        b[x]++;
    }
    f[0][0][0][0]=a[0];
    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){
                    int t=a[i+j*2+k*3+l*4];
                    int &v=f[i][j][k][l];
                    if(i) v=max(v,f[i-1][j][k][l]+t);
                    if(j) v=max(v,f[i][j-1][k][l]+t);
                    if(k) v=max(v,f[i][j][k-1][l]+t);
                    if(l) v=max(v,f[i][j][k][l-1]+t);
                }
            }
        }
    }
    cout<<f[b[1]][b[2]][b[3]][b[4]]<<endl;
    return 0;
}