比赛 Asm.Def战记之圣地亚哥“杯2015 评测结果 AAAAAAAAAA
题目名称 Asm.Def的枪榴弹 最终得分 100
用户昵称 fyb 运行时间 0.008 s
代码语言 C++ 内存使用 0.48 MiB
提交时间 2015-10-31 10:24:06
显示代码纯文本
#include <cstdio>

using namespace std;

#define NMAX 14
#define NUM 20000

struct st{int jia,yi,bing;};

int n,dfs_mx;
int a[NMAX],b[NMAX],c[NMAX],d[NMAX],e[NMAX];
st dp[NUM];
bool vis[NUM];

bool bu_hui_si(int ind,st num){
	if(a[ind]<=num.jia)return (b[ind]<=num.yi+num.bing);
	else return (b[ind]<=num.jia+num.yi+num.bing-a[ind]);
}

st sheng_duo_shao(int ind,st num){
	st ans;

	ans=num;
	if(a[ind]<=ans.jia)ans.jia-=a[ind];
	else{
		ans.bing-=a[ind]-ans.jia;
		ans.jia=0;
	}
	if(b[ind]<=ans.yi)ans.yi-=b[ind];
	else{
		ans.bing-=b[ind]-ans.yi;
		ans.yi=0;
	}
	ans.jia+=c[ind];
	ans.yi+=d[ind];
	ans.bing+=e[ind];
	return ans;
}

st dfs(int ind){
	st tst,ans=(st){0,0,0};
	int tmp,mx=0;
	int i;

	if(vis[ind])return dp[ind];
	vis[ind]=true;

	for(i=0;i<n;i++)
		if(ind&(1<<i)){
//			printf("%d\n",ind&~(1<<i));
			tst=dfs(ind&~(1<<i));
			if(bu_hui_si(i,tst)){
				tst=sheng_duo_shao(i,tst);
				if((tmp=tst.jia+tst.yi+tst.bing)>mx){
					mx=tmp;
					ans=tst;
					if(tmp>dfs_mx)dfs_mx=tmp;
				}
			}
		}
//	printf("%x %d %d %d\n",ind,ans.jia,ans.yi,ans.bing);
	return dp[ind]=ans;
}

int main(){
	int k0,k1,k2;
	int dp_end=0;
	int i;

	freopen("asm_grenade.in","r",stdin);
	freopen("asm_grenade.out","w",stdout);

	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	for(i=0;i<n;i++)scanf("%d",b+i);
	for(i=0;i<n;i++)scanf("%d",c+i);
	for(i=0;i<n;i++)scanf("%d",d+i);
	for(i=0;i<n;i++)scanf("%d",e+i);
	scanf("%d%d%d",&k0,&k1,&k2);

	dp[0]=(st){k0,k1,k2};
	vis[0]=true;
	for(i=0;i<n;i++)
		dp_end|=1<<i;
	dfs_mx=k0+k1+k2;

	dfs(dp_end);

	printf("%d\n",dfs_mx);
//	printf("%d\n",sheng_duo_shao(1,(st){2,1,3}).yi);
	return 0;
}