1001.cpp

HDOJ 5月2日 “老菜鸟杯”程序大赛标准程序+解题报告

#include<stdio.h>
#include<string>
#include<stdlib.h>
//////////////////////////////////////////////////////////////////////////
struct Hero{
	int ati;
	int def;
	int hp;
	int exp;
};
Hero lb,emery[21],inc;
int dp[1<<20];
int n,maxn;
//////////////////////////////////////////////////////////////////////////
int lowbit(int x) {
	return (x&(x-1))==0;
}
int Max(int a,int b) {
	return a>b?a:b;
}
int fight(Hero A,Hero B)
{
	int time,hp;
	int pow = Max(1,A.ati - B.def);
	time = B.hp / pow;
	if(pow * time == B.hp)
		time --;
	pow = Max(1,B.ati - A.def);
	hp = A.hp - time * pow;
	if(hp>0)
		return hp;
	else
		return 0;
}
int dfs(int maxn)
{
	int max,idx,hp,exp;
	int buf;
	Hero now;
	if(lowbit(maxn))
	{
		idx = -1;
		while(maxn) {
			idx ++;
			maxn >>= 1;
		}
		hp = fight(lb,emery[idx]);
		dp[maxn] = hp;
		return dp[maxn];
	}

	exp = 0;
	for(idx = 0;idx < n;idx ++)
	{
		buf = 1 << idx;
		if((maxn & buf) == buf)
			exp += emery[idx].exp;
	}

	max = 0;
	for(idx = 0;idx < n ; idx ++)
	{
		buf = 1 << idx;
		if((maxn & buf) == buf)
		{
			now.exp = exp - emery[idx].exp;
			if(dp[maxn - buf] != -1)
				now.hp = dp[maxn - buf];
			else
				now.hp = dfs(maxn - buf);
			now.ati = lb.ati + now.exp / 100 * inc.ati;
			now.def = lb.def + now.exp / 100 * inc.def;
			hp = fight(now,emery[idx]);
			if(hp && exp / 100 > now.exp / 100)
				hp += inc.hp;
			if(hp > max)
				max = hp;
		}
	}

	dp[maxn] = max;
	return dp[maxn];
}
//////////////////////////////////////////////////////////////////////////
int main()
{
// 	freopen("in.in","r",stdin); 
//  freopen("out.out","w",stdout);
	int i,ans;
	char name[21];
	while(scanf("%d%d%d",&lb.ati,&lb.def,&lb.hp)==3)
	{
		lb.exp = 0;
		scanf("%d%d%d",&inc.ati,&inc.def,&inc.hp);
		scanf("%d",&n);
		for(i=0;i<n;i++) {
			scanf("%s",name);
			scanf("%d%d%d%d",&emery[i].ati,&emery[i].def,&emery[i].hp,&emery[i].exp);
		}
		maxn = (1 << n) - 1;
		memset(dp,-1,sizeof(int)*maxn);
		ans = dfs(maxn);
		if(ans==0)
			puts("Poor LvBu,his period was gone.");
		else
			printf("%d\n",ans);
	}
	return 0;
}