记录编号	418209	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]乌龟棋	最终得分	100
用户昵称	玉带林中挂	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2017-06-29 17:10:10	内存使用	11.09 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[41][41][41][41];
int s[351];
int max(int a,int b)
{
	if (a>b) return a;
	else return b;
}
int main()
{
	freopen("tortoise.in","r",stdin);
	freopen("tortoise.out","w",stdout);
	int n,m,x;
	cin>>n>>m;//n和m分别表示棋盘格子数和爬行卡片数
	int a=0,b=0,c=0,d=0;
	for(int i=0;i<n;i++)
	   cin>>s[i];//ai表示棋盘第i个格子上的分数
    for(int i=1;i<=m;i++)
    /*每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。*/
    {
       cin>>x;
       if(x==1)a++;
       if(x==2)b++;
       if(x==3)c++;
       if(x==4)d++;
    }
    for(int i=0;i<=a;i++)
       for(int x=0;x<=b;x++)
          for(int y=0;y<=c;y++)
             for(int z=0;z<=d;z++)
                {
                	if(i!=0)f[i][x][y][z]=max(f[i][x][y][z],f[i-1][x][y][z]);
                	if(x!=0)f[i][x][y][z]=max(f[i][x][y][z],f[i][x-1][y][z]);
                	if(y!=0)f[i][x][y][z]=max(f[i][x][y][z],f[i][x][y-1][z]);
                	if(z!=0)f[i][x][y][z]=max(f[i][x][y][z],f[i][x][y][z-1]);
                	f[i][x][y][z]+=s[i+x*2+y*3+z*4];
                }
    cout<<f[a][b][c][d];
    fclose(stdin);
	fclose(stdout);
	return 0;
}