比赛 20090916练习赛 评测结果 AWATTAAAAA
题目名称 护卫队 最终得分 70
用户昵称 magic 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-21 21:26:08
显示代码纯文本
#include<iostream>
#include<cstdio>
#define maxlong 100000
using namespace std;
	int shv[1005][1005];
	int w[1005];
	int sw[1005];
	int v[1005];
	double f[1005][1005];
	int wei,len,n,m,i,j,k;
	double ans;
double mind(double x,double y);
double mind(double x,double y)
{
	if (x<y) return x;else return y;
}
int main()
{
	freopen("convoy.in","r",stdin);
	freopen("convoy.out","w",stdout);
	scanf("%d%d%d",&wei,&len,&n);
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			f[i][j]=maxlong;
		}
	}
	for (i=1;i<=n;i++)
	{
		scanf("%d%d",&w[i],&v[i]);
		shv[i][i]=v[i];
		sw[i]=sw[i-1]+w[i];
	}
	for (i=1;i<=n-1;i++)
	{
		for (j=i+1;j<=n;j++)
		{
		shv[i][j]=maxlong;
		shv[i][j]=min(shv[i][j-1],v[j]);
		}
	}
	for (i=1;i<=n;i++)
	{
		if (sw[i]<=wei)
		{
		f[i][1]=float(len)/(shv[1][i]);
		}
	}
	for (i=2;i<=n;i++)
	{
		for (j=2;j<=i;j++)
		{
			int sum=0;
			m=i;
			while (sum+w[m]<=wei&&m>0)
			{
				sum+=w[m];
				m--;
			}
			for (k=m;k<=i;k++)
			{
				if (j-1<=k&&f[k][j-1]!=0)
				{
				f[i][j]=mind(f[i][j],f[k][j-1]+float(len)/(shv[k+1][i]));	
				}
			}
		}
	}
	ans=maxlong;
	for (int i=1;i<=n;i++)
	{
		ans=mind(ans,f[n][i]);
	}
	printf("%0.1f",ans*60);
	return 0;
}