记录编号	27433	评测结果	AAAAAAAAAA
题目名称	护卫队	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.068 s
提交时间	2011-09-22 14:51:15	内存使用	0.26 MiB

#include <fstream>
#include <iomanip>
#include <cfloat>

#define I_F "convoy.in"
#define O_F "convoy.out"

const int MAXn=1000;

double **v;
int n, l;
long long *w,m;
double ans;

void Input();
void Dynap();
void Output();

int main()
{
	Input();
	Dynap();
	Output();
	delete []v;
	delete []w;
	return 0;
}

void Input()
{
	std::ifstream fin(I_F);
	fin>>m>>l>>n;
	double tv;
	long tw;
	v=new double*[n+1];
	for (int i=0; i<=n; i++)
		v[i]=new double[n+1];
	w=new long long[n+1];
	w[0]=0;
	for (int i=1; i<=n; i++)
	{
		fin>>tw>>tv;
		tv=((double)l)/(tv/(double)60);
		w[i]=w[i-1]+tw;
		v[i][i]=tv;
	}
	fin.close();
	
	for (int i=1; i<n; i++)
		for (int j=i+1; j<=n; j++)
			v[i][j]=(v[i][j-1]>v[j][j])?v[i][j-1]:v[j][j];
}

void Dynap()
{
	double *f=new double[n+1];
	f[0]=0, f[1]=v[1][1];
	for (int i=2; i<=n; i++)
	{
		f[i]=DBL_MAX;
		for (int j=i; (j>0)&&(w[i]-w[j-1]<=m); j--)
			f[i]=(f[i]<(f[j-1]+v[j][i]))?f[i]:(f[j-1]+v[j][i]);
	}
	ans=f[n];
	delete []f;
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<setiosflags(std::ios::fixed)<<std::setprecision(1)<<ans<<std::endl;
	fout.close();
}