题目链接
直接拿来当贪心做了=_=,然后就懵逼了
动态规划,本弱真没想到=_=
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double eps = 0.000001;
const int INF = 0xffffff;
int station[];
double dp[];
int l, n, c, t, vr, vt1, vt2;
double get_time(int s, int tempc)
{
double gtime = ;
if(s > tempc)
{
gtime += 1.0 * tempc / vt1;
gtime += (s - tempc) * 1.0 / vt2;
}
else
{
gtime += s * 1.0 / vt1;
}
return gtime;
}
int is_chong(int s, int tempc)
{
double chong_time = t + get_time(s, c);
double not_chong_time = get_time(s, tempc);
if(not_chong_time - chong_time > eps)
return ;
return ;
}
double get_min(double x, double y)
{
if(x - y > eps)
return y;
return x;
}
int main()
{
while(scanf("%d", &l) != EOF)
{
scanf("%d%d%d", &n, &c, &t);
scanf("%d%d%d", &vr, &vt1, &vt2);
for(int i = ; i <= n; i++)
scanf("%d", &station[i]);
station[n + ] = l;
double rtime = 1.0 * l / vr;
station[] = ;
dp[] = ;
for(int i = ; i <= n + ; i++)
{
dp[i] = INF;
for(int j = i - ; j >= ; j--)
{
double tempTime = ;
int s = station[i] - station[j];
if(s > c)
{
tempTime = 1.0 * c / vt1;
tempTime += (s - c) * 1.0 / vt2;
}
else
tempTime = s * 1.0 / vt1;
if(j)
tempTime += t;
dp[i] = get_min(dp[i], dp[j] + tempTime);
}
/*
int s = station[i] - station[i - 1];
if(s > tempc)
{
gtime += 1.0 * tempc / vt1;
gtime += (s - tempc) * 1.0 / vt2;
tempc = 0;
}
else
{
gtime += s * 1.0 / vt1; // 不知道什么时候手贱,这里把s写成了c,浪费了半个小时
tempc = tempc - s;
}
if(is_chong(station[i + 1] - station[i], tempc))
{
gtime += t;
tempc = c;
}
*/
}
//gtime += get_time(l - station[n], tempc);
if(dp[n + ] - rtime > eps)
printf("Good job,rabbit!\n");
else
printf("What a pity rabbit!\n");
}
return ;
}