【题目大意】
【思路】
最简单的思路是五维数组，但是当前走到的步数由已经取到的卡片决定，所以只需要四维。本来想要改一个滚动数组的，但是好像没有滚起来，算了(ノ｀Д)ノ。
在学校要晚自习到21:15，回到家大概就22:00了，本来每天晚上想要切题的但是想到第二天五点多又要起床了，算了orz在努力问老师讨机房钥匙，虽然并没有成功。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=350+5; 7 const int MAXM=120+5; 8 int n,m;//棋子的数量和卡片的数量 9 int a[MAXN];//每一格的分数 10 int num[4]; 11 int f[MAXM][MAXM][MAXM][MAXM];//四张卡片分别取这四张时候的最多得分 12 13 int main() 14 { 15 //freopen("tortoise1.in","r",stdin); 16 scanf("%d%d",&n,&m); 17 for (int i=0;i<n;i++) scanf("%d",&a[i]); 18 /*因为起点是第一个格子，所以下标从零开始设*/ 19 for (int i=0;i<m;i++) 20 { 21 int t; 22 scanf("%d",&t); 23 num[t-1]++; 24 } 25 cout<<num[3]<<endl; 26 memset(f,0,sizeof(f)); 27 for (int i1=0;i1<=num[0];i1++) 28 for (int i2=0;i2<=num[1];i2++) 29 for (int i3=0;i3<=num[2];i3++) 30 for (int i4=0;i4<=num[3];i4++) 31 { 32 int score=a[i1+i2*2+i3*3+i4*4]; 33 f[i1][i2][i3][i4]=0; 34 if (i1>0) f[i1][i2][i3][i4]=max(f[i1-1][i2][i3][i4],f[i1][i2][i3][i4]); 35 if (i2>0) f[i1][i2][i3][i4]=max(f[i1][i2-1][i3][i4],f[i1][i2][i3][i4]); 36 if (i3>0) f[i1][i2][i3][i4]=max(f[i1][i2][i3-1][i4],f[i1][i2][i3][i4]); 37 if (i4>0) f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4-1],f[i1][i2][i3][i4]); 38 f[i1][i2][i3][i4]+=score; 39 } 40 cout<<f[num[0]][num[1]][num[2]][num[3]]<<endl; 41 42 return 0; 43 }