原题
不能用贪心，那么就是线性dp，难点在于如何表示状态，因为牌的种类只有4种，所以开一个五维数组分别表示位置、不同牌的牌数即可。可以优化一维，因为牌的总数已知，m-3种牌数=另外一种牌的数量。
我写的是递推式，因为牌数刚好用完，直接输出f[n][0][0][0]。
#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; short n,m,v[351],pai[5];short f[351][41][41][41]; short maxx(short a,short b) { if(a>b) return a; else return b; } int main() { int a; cin>>n>>m; for(int i=1;i<=n;++i) cin>>v[i]; memset(pai,0,sizeof(pai)); for(int i=1;i<=m;++i) { cin>>a; pai[a]++; }int p=pai[4]; for(int i=1;i<=n;++i) for(int j=0;j<=pai[1];++j) for(int k=0;k<=pai[2];++k) for(int z=0;z<=pai[3];++z) f[i][j][k][z]=-999; f[1][pai[1]][pai[2]][pai[3]]=v[1]; for(int i=1;i<=n;++i) for(int j=0;j<=pai[1];++j) for(int k=0;k<=pai[2];++k) for(int z=0;z<=pai[3];++z) { if(f[i][j][k][z]<0) continue; if(j>0) f[i+1][j-1][k][z]=maxx(f[i+1][j-1][k][z],f[i][j][k][z]+v[i+1]); if(k>0) f[i+2][j][k-1][z]=maxx(f[i+2][j][k-1][z],f[i][j][k][z]+v[i+2]); if(z>0) f[i+3][j][k][z-1]=maxx(f[i+3][j][k][z-1],f[i][j][k][z]+v[i+3]); if(m-j-k-z>0) f[i+4][j][k][z]=maxx(f[i+4][j][k][z],f[i][j][k][z]+v[i+4]); } cout<<f[n][0][0][0]; return 0; }
