https://www.luogu.org/problemnew/show/P1541

2年前做过这道题，不过早就忘了怎么做的了。

看到题，先想到用f(p,i,j,k,l)表示当前在位置p，手中有i,j,k,l张四种面值的卡片，已经得到的分数，

则f(p,i,j,k,l)=max{f(p-1,i+1,j,k,l),f(p-2,i,j+1,k,l),f(p-3,i,j,k+1,l),f(p-4,i,j,k,l+1)}+score(p).

没分析复杂度，结果开始炸了空间，想到空间要350*40^4，就把第一维数组改成循环滚动5个就够了，结果交上去TLE，啊时间也是350*40^4的。

实际上，五维的状态有冗余，当前的位置可以由(i,j,k,l)唯一表示，故改成四维。

设f(i,j,k,l):已经分别使用四张卡片的张数

f[i,j,k,l]:=max{f[i-1,j,k,l]f[i,j-1,k,l],f[i,j,k-1,l],f[i,j,k,l-1]}+a[x]，x=1+i+j*2+k*3+l*4

边界是f(0,0,0,0)=a(1)

#include<bits/stdc++.h>
using namespace std;
#define INF (1<<30)
int n,m,a[355],x,tot[5];
int f[45][45][45][45];

int Max(int a,int b,int c,int d)
{
	int x=max(a,b),y=max(c,d);
	return max(x,y);
}

int main()
{
	freopen("input.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>x,tot[x]++;
		for(int i=0;i<=tot[1];i++)
			for(int j=0;j<=tot[2];j++)
				for(int k=0;k<=tot[3];k++)
					for(int l=0;l<=tot[4];l++)
					{        
						f[i][j][k][l]=a[1+i+2*j+3*k+4*l]+Max(f[max(i-1,0)][j][k][l],
						  f[i][max(j-1,0)][k][l],f[i][j][max(k-1,0)][l],f[i][j][k][max(l-1,0)]);		
					}
//这里顺便把存在ijkl=0时-1小于0数组越界的情况也处理了，因为每个状态初始值为0，
//越界的那一个子状态处理为它本身即0即可。比较的四个
//子状态实际上是max(_,_,_,0)，使得不受边界之外的影响。
//写4个if也可以                          
	cout<<f[tot[1]][tot[2]][tot[3]][tot[4]]<<endl;
	return 0;
}