记录编号	301868	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]乌龟棋	最终得分	100
用户昵称	Janis	是否通过	通过
代码语言	C++	运行时间	0.133 s
提交时间	2016-09-02 18:37:26	内存使用	10.08 MiB

/*状态定义：dp[i][j][k][l]表示使用i张1卡,j张2卡,k张3卡,l张4卡时所能得到的最大分数。
转移方程：dp[i][j][k][l]=max{dp[i-1][j][k][l]+w[d-1],dp[i][j-1][k][l]+w[d-2],dp[i][j][k-1][l]+w[d-3],dp[i][j][k][l-1]+w[d-4]}
其中d=i+j*2+k*3+l*4;且i,j,k,l大于0时进行转移 
边界：dp[0][0][0][0]=w[0];dp[num_of_1][num_of_2][num_of_3][num_of_4]为最大分值。*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define COGS
using namespace std;
int n,m;
int dp[40][40][40][40];
int w[400];
int e[5];
void Init(){
	int a;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)scanf("%d",&w[i]);
	for(int i=0;i<m;i++){
		scanf("%d",&a);
		e[a]++;
	}
}
void Work(){
	dp[0][0][0][0]=w[0];
	for(register int i=0;i<=e[1];i++)
		for(register int j=0;j<=e[2];j++)
			for(register int k=0;k<=e[3];k++)
				for(register int l=0;l<=e[4];l++){
					int d=i+j*2+k*3+l*4;
					//dp[i][j][k][l]=max(max(dp[i-1][j][k][l]+w[d-1],dp[i][j-1][k][l]+w[d-2]),max(dp[i][j][k-1][l]+w[d-3],dp[i][j][k][l-1]+w[d-4]));
					if(i)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l]+w[d]);
					if(j)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-1][k][l]+w[d]);
					if(k)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l]+w[d]);
					if(l)dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k][l-1]+w[d]);
				}
	printf("%d",dp[e[1]][e[2]][e[3]][e[4]]);
}
int main()
{
	#ifdef COGS
		string FileName="tortoise";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	Init();
	Work();
}