比赛 防止颓废的小练习v0.2 评测结果 AAAAAAAAAA
题目名称 乌龟棋 最终得分 100
用户昵称 农场主 运行时间 0.330 s
代码语言 C++ 内存使用 92.57 MiB
提交时间 2016-10-18 19:33:47
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 41
using namespace std;
int d[351][maxn][maxn][maxn]={0};
int v[351]={0};
int c[5]={0},n,m,ans=0;
int num(int s,int a2,int a3,int a4){
	return s-a2*2-a3*3-a4*4;
}
void read(){
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	for (int i=1;i<=m;i++){
		int p;
		scanf("%d",&p);
		c[p]++;
	}
}
bool check(int x,int a2,int a3,int a4){
	int a1=num(x,a2,a3,a4);
	if (a1<0) return 0;
	if (a1>c[1]||a2>c[2]||a3>c[3]||a4>c[4]) return 0;
	return 1;
}
void update(int x,int a2,int a3,int a4){
	int& now=d[x][a2][a3][a4];
	if (x-1>=0) now=max(now,d[x-1][a2][a3][a4]+v[x]);
	if (x-2>=0&&a2>0) now=max(now,d[x-2][a2-1][a3][a4]+v[x]);
	if (x-3>=0&&a3>0) now=max(now,d[x-3][a2][a3-1][a4]+v[x]);
	if (x-4>=0&&a4>0) now=max(now,d[x-4][a2][a3][a4-1]+v[x]);
	ans=max(ans,now);
}
int main(){
	freopen("tortoise.in","r",stdin);
	freopen("tortoise.out","w",stdout);
	read();
//	printf("%d %d %d %d\n",c[1],c[2],c[3],c[4]);
	d[0][0][0][0]=v[0];
	for (int i=1;i<n;i++){
		for (int j=0;j<=c[2];j++){
			if (j*2>i) break;
			for (int k=0;k<=c[3];k++){
				if (j*2+k*3>i) break;
				for (int l=0;l<=c[4];l++){
					if (j*2+k*3+l*4>i) break;
//					printf("%d\n",check(i,j,k,l));
					if (check(i,j,k,l)){
						update(i,j,k,l);
//						printf("%d %d %d %d %d\n",i,num(i,j,k,l),j,k,l);
					}
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}