记录编号	305938	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]乌龟棋	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.252 s
提交时间	2016-09-11 14:18:17	内存使用	15.94 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=360,maxm=45;
int dfs(int,int,int,int);
int f[maxm][maxm][maxm][maxm]={{{{0}}}};
int n,m,w[maxn],x,A=0,B=0,C=0,D=0;
int main(){
#define MINE
#ifdef MINE
	freopen("tortoise.in","r",stdin);
	freopen("tortoise.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	while(m--){
		scanf("%d",&x);
		if(x==1)A++;
		else if(x==2)B++;
		else if(x==3)C++;
		else D++;
	}
	printf("%d",dfs(0,0,0,0));
#ifdef MINE
	fclose(stdin);
	fclose(stdout);
#else
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
int dfs(int a,int b,int c,int d){
	if(f[a][b][c][d])return f[a][b][c][d];
	if(a<A)f[a][b][c][d]=max(f[a][b][c][d],dfs(a+1,b,c,d));
	if(b<B)f[a][b][c][d]=max(f[a][b][c][d],dfs(a,b+1,c,d));
	if(c<C)f[a][b][c][d]=max(f[a][b][c][d],dfs(a,b,c+1,d));
	if(d<D)f[a][b][c][d]=max(f[a][b][c][d],dfs(a,b,c,d+1));
	return f[a][b][c][d]+=w[a+b*2+c*3+d*4+1];
}