比赛 20090916练习赛 评测结果 AAWWWAWWWA
题目名称 护卫队 最终得分 40
用户昵称 超级傲娇的AC酱 运行时间 0.017 s
代码语言 C++ 内存使用 3.28 MiB
提交时间 2013-11-07 21:01:45
显示代码纯文本
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fi("convoy.in");
ofstream fo("convoy.out");
int main()
{
	int W,n,w[1001],i,j;
    double T[1001],v[1001],L,V;
	fi>>W>>L>>n;
    for(i=0;i<n;i++)
		fi>>w[i]>>v[i];
	T[0]=L/v[0];
	
	for(i=1;i<n;i++)
	{
		int wei=w[i];
		T[i]=T[i-1]+L/v[i];
		V=v[i];
		for(j=i-1;j>=0;j--)
		{
			
			if(wei>W)break;
			T[i]=min(T[i],T[j]+L/V);wei+=w[j];
			V=min(V,v[j]);
		}
	}
	
	fo<<setiosflags(ios::fixed)<<setprecision(1)<<T[n-1]*60;
	return 0;
}