记录编号	7532	评测结果	AAAAAAAAAA
题目名称	地精贸易	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.293 s
提交时间	2008-11-10 16:48:53	内存使用	7.13 MiB

#include <iostream>
#include <stdlib.h>

#define MAXN 102
#define MAXV 900010

using namespace std;

int n,v,num[2],data[MAXN][2],c[2][MAXN],w[2][MAXN],buymany[2][MAXN],f[MAXV],use[MAXV]={0};


void dp(int st)
{
	int i,j;
	for (j=0;j<=v;j++)
	{
		for (i=1;i<=num[st];i++)
		{
			if (j-c[st][i]>=0)
			{
				if (f[j-c[st][i]]+w[st][i]>f[j])
				{
					f[j]=f[j-c[st][i]]+w[st][i];
					use[j]=i;
                }
			}
		}
	}
	j=v;
	while (use[j]!=0)
	{
          buymany[st][use[j]]++;
          j-=c[st][use[j]];

    }
}

void ini()
{
	int i,j,a,b,flag,ans=0;
	cin>>v>>n;
	for (i=1;i<=n;i++)
	{
		cin>>a>>b;
		data[i][0]=a;
		data[i][1]=b;
		flag=1;
		if (flag==0)
			continue;
		if (a<b)
		{
			//st 0
			num[0]++;
			c[0][num[0]]=a;
			w[0][num[0]]=b-a;
		}
		if (a>b)
		{
			//st 1
			num[1]++;
			c[1][num[1]]=b;
			w[1][num[1]]=a-b;
		}
	}
	dp(0);
	ans=f[v];
	v+=f[v];
	memset(f,0,sizeof(f));
	memset(use,0,sizeof(use));
	dp(1);
	printf("%d\n",f[v]+ans);
}

void print()
{
	int i,p=0,q=0;
	for (i=1;i<=n;i++)
	{
		if (data[i][0]<data[i][1])
		{
			p++;
			if (buymany[0][p]==0)
				cout<<"Buy 0";
			else
				cout<<"Buy "<<buymany[0][p]<<" from Alliance";
		}
		if (data[i][0]>data[i][1])
		{
			q++;
			if (buymany[1][q]==0)
				cout<<"Buy 0";
			else
				cout<<"Buy "<<buymany[1][q]<<" from Horde";
		}
		if (data[i][0]==data[i][1])
		{
			cout<<"Buy 0";
		}
		if (i!=n)
			cout<<endl;
	}
}

int main()
{
	freopen("goblin.in","r",stdin);
	freopen("goblin.out","w",stdout);
	ini();
	print();
	return 0;
}