记录编号	7825	评测结果	AAAAAAAAAA
题目名称	[BYVoid S3] 阿鲁高的远航	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.375 s
提交时间	2008-11-11 20:44:48	内存使用	11.94 MiB

#include <iostream>

#define MAXN 1010
#define INF 99999999

using namespace std;

int t,v,a,w,ans,rob[MAXN],need[MAXN],pay[MAXN],f[MAXN][MAXN],use[MAXN][MAXN],last[MAXN][MAXN];


void run()
{
	int i,j,k,zan;
	for (i=0;i<MAXN;i++)
		for (j=0;j<MAXN;j++)
			f[i][j]=INF;
	f[0][0]=0;
	for (i=1;i<=t;i++)
		for (j=0;j<=v;j++)
		{
			for (k=0;k<=v;k++)
			{
				zan=need[i]+j-k;
				if (zan>=0 && zan<=a)
				{
					if (f[i-1][k]+zan*pay[i]<f[i][j])
					{
						f[i][j]=f[i-1][k]+zan*pay[i];
						use[i][j]=zan;
						last[i][j]=k;
					}
				}
			}
			if (f[i][j]<INF)
				f[i][j]+=j*w;
		}
	ans=INF;
	for (j=0;j<=v;j++)
		if (f[t][j]<ans)
		{
			ans=f[t][j];
			k=j;
		}
	cout<<ans<<endl;
	for (i=t;i>=1;i--)
	{
		rob[i]=use[i][k];
		k=last[i][k];
	}
	for (i=1;i<=t;i++)
	{
		cout<<rob[i];
		if (i!=t)
			cout<<endl;
	}
}

void ini()
{
	int i;
	cin>>t>>v>>a>>w;
	for (i=1;i<=t;i++)
	{
		cin>>need[i]>>pay[i];
	}
}

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