比赛 |
20090916练习赛 |
评测结果 |
AWAWWAAAAA |
题目名称 |
护卫队 |
最终得分 |
70 |
用户昵称 |
Citron酱 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-09-21 20:08:11 |
显示代码纯文本
#include <fstream>
#include <iomanip>
#define I_F "convoy.in"
#define O_F "convoy.out"
const int MAXn=1000;
const double DOUB_MAX=100000000;
double **v;
int n, l;
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[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]=DOUB_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();
}