记录编号	371869	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]乌龟棋	最终得分	100
用户昵称	+1s	是否通过	通过
代码语言	C++	运行时间	0.138 s
提交时间	2017-02-17 08:49:31	内存使用	24.16 MiB

#include<fstream>
using namespace std;
ifstream fin("tortoise.in");
ofstream fout("tortoise.out");
int n,m,a[355],b[125],c1,c2,c3,c4,memo[50][50][50][50];
int d(int cc1,int cc2,int cc3,int cc4)
{
	if(memo[cc1][cc2][cc3][cc4]!=0)
	return memo[cc1][cc2][cc3][cc4];
	if(cc1==0&&cc2==0&&cc3==0&&cc4==0)
	return a[1];
	int x=n-(c1-cc1+(c2-cc2)*2+(c3-cc3)*3+(c4-cc4)*4);
	int t1,t2,t3,t4;
	t1=t2=t3=t4=0;
	if(cc1>0)
	t1=d(cc1-1,cc2,cc3,cc4);
	if(cc2>0)
	t2=d(cc1,cc2-1,cc3,cc4);
	if(cc3>0)
	t3=d(cc1,cc2,cc3-1,cc4);
	if(cc4>0)
	t4=d(cc1,cc2,cc3,cc4-1);
	int m=t1;
	if(t2>m)
	m=t2;
	if(t3>m)
	m=t3;
	if(t4>m)
	m=t4;
	return memo[cc1][cc2][cc3][cc4]=m+a[x];
}
int main()
{
	fin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		fin>>a[i];
	}
	for(int j=1;j<=m;j++)
	{
		int t;
		fin>>t;
		switch(t)
		{
			case 1:
				c1++;
				break;
			case 2:
				c2++;
				break;
			case 3:
				c3++;
				break;
			case 4:
				c4++;
				break;
		}
	}
	int r=d(c1,c2,c3,c4);
	fout<<r;
	return 0;
}