比赛 20090916练习赛 评测结果 AWAWWAAAAA
题目名称 护卫队 最终得分 70
用户昵称 Truth.Cirno 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-10-17 20:28:35
显示代码纯文本
#include <cstdio>
using namespace std;

double arrmax(double a[],int l,int r)
{
	int i;
	double minnum=-1;
	for (i=l;i<=r;i++)
		if (minnum<a[i])
			minnum=a[i];
	return(minnum);
}

int main(void)
{
	freopen("convoy.in","r",stdin);
	freopen("convoy.out","w",stdout);
	const int MAXINT=1000000000;
	int i,j,maxwei,maxlen,n,wei[1000]={0},weisum[1000]={0},temp;
	double ftemp,tim[1000]={0},f[1000]={0};
	scanf("%d %d %d",&maxwei,&maxlen,&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d %d",&wei[i],&temp);
		weisum[i]=weisum[i-1]+wei[i];
		tim[i]=double(maxlen)/double(temp)*60.0;
		f[i]=MAXINT;
	}
	temp=0;
	i=1;
	while (i<=n)
	{
		for (j=temp;j<=i-1;j++)
		{
			ftemp=arrmax(tim,j+1,i)+f[j];
			if (f[i]>ftemp)
				f[i]=ftemp;
		}
		i++;
		while (weisum[i]-weisum[temp]>maxwei)
			temp++;
	}
	printf("%.1lf\n",f[n]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}