动态规划 线性dp$(40^4)$

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=360,M=45;
int w[N];
int f[M][M][M][M]; //f[A][B][C][D]表示用了A张卡片1,B张卡片2,C张卡片3,D张卡片4的方案数
int s[10];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) //获取卡片的值
	{
		cin>>w[i];
	}
	for(int i=1;i<=m;i++) //获取每种卡片的数量
	{
		int x;
		cin>>x;
		s[x]++;
	}
	f[0][0][0][0]=w[1]; //初始化入口
	for(int A=0;A<=s[1];A++)
	{
		for(int B=0;B<=s[2];B++)
		{
			for(int C=0;C<=s[3];C++)
			{
				for(int D=0;D<=s[4];D++)
				{
					int t=w[1+A+B*2+C*3+D*4]; //用了卡片以后走到的位置
					int &v=f[A][B][C][D];
					v=t; //至少会有这个位置的分数
					if(A) v=max(v,f[A-1][B][C][D]+t);
					if(B) v=max(v,f[A][B-1][C][D]+t);
					if(C) v=max(v,f[A][B][C-1][D]+t);
					if(D) v=max(v,f[A][B][C][D-1]+t);
				}
			}
		}
	}
	cout<<f[s[1]][s[2]][s[3]][s[4]];
	return 0;
}