一道线型dp的题目
每一种卡片有一定的数量限制，也就是说在计算到某一个状态时应当知道每一个卡片能不能用，所以我们定义状态f[i][j][k][l]表示第一种卡片用i张，第二张卡片用j张……所得到的最大值。
对于每一个状态，考虑他是怎样转移的。若当前状态为f[i][j][k][l]，那么当前的状态可以是f[i-1][j][k][l]使用一张1号卡片得到的，也可以是f[i][j-1][k][l]用一张2号卡片得到的，以此类推。
因此，我们枚举每一种卡片使用的数量即可完成状态转移。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 inline int read() { 8 int ret=0; 9 int op=1; 10 char c=getchar(); 11 while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();} 12 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 13 return ret*op; 14 } 15 int n,m,a[360],num[5],f[50][50][50][50]; 16 int main() { 17 scanf("%d%d",&n,&m); 18 for(int i=1;i<=n;i++) { 19 a[i]=read(); 20 } 21 for(int i=1;i<=m;i++) { 22 num[read()]++; 23 } 24 f[0][0][0][0]=a[1]; 25 for(int i=0;i<=num[1];i++) 26 for(int j=0;j<=num[2];j++) 27 for(int k=0;k<=num[3];k++) 28 for(int l=0;l<=num[4];l++) { 29 int now=i+j*2+k*3+l*4+1; 30 if(i) f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[now]); 31 if(j) f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[now]); 32 if(k) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[now]); 33 if(l) f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[now]); 34 } 35 printf("%d ",f[num[1]][num[2]][num[3]][num[4]]); 36 return 0; 37 }