HDU 2059 龟兔赛跑

时间：2023-03-09 03:22:32
HDU 2059 龟兔赛跑

受上一道题影响，我本来想着开一个二维数组来表示充电和不充电的状态。

可这样就有一个问题，如果没有充电，那么在下一个阶段就有剩余的电量。

这样问题貌似就不可解了，难道是因为不满足动态规划的无后效性这一条件？

这里先打个问号。

所以这题还是看的别人的思路。

将起点和终点划分到N个加电站中去

这样一共有N+2点,用DP[i]表示到第i个加电站的最小耗费时间

那么在求DP[i]的时候，DP[0]...DP[i-1]已经求得

让j从0遍历到i-1,每一个j表示最后一次充电到i点

那么状态转移方程为

DP[i] = min(DP[j] + t(j, i)) //t(j, i)表示从j充完电一直到i点(中途没有充过电)

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 double p[];

 double dp[];

 int main(void)

 {

     #ifdef LOCAL

         freopen("2059in.txt", "r", stdin);

     #endif

     int l;

     while(scanf("%d", &l) != EOF)

     {

         int i, j;

         int n, c, t;

         double vr, vt1, vt2;

         double temp;

         memset(dp, , sizeof(dp));

         memset(p, , sizeof(p));

         scanf("%d%d%d", &n, &c, &t);

         scanf("%lf%lf%lf", &vr, &vt1, &vt2);

         for(i = ; i <= n; ++i)

         {

             scanf("%lf", &p[i]);

         }

         p[] = ;

         p[n + ] = l;

         dp[] = ;

         for(i = ; i <= n + ; ++i)

         {

             dp[i] = ;

             for(j = ; j < i; ++j)

             {

                 double lenth = p[i] - p[j];

                 if(c >= lenth)

                     temp = dp[j] + lenth / vt1;

                 else

                     temp = dp[j] + c / vt1 + (lenth - c) / vt2;

                 if(j > )

                     temp += t;

                 if(temp < dp[i])

                     dp[i] = temp;

             }

         }

         if(dp[n + ] < (l / vr))

             printf("What a pity rabbit!\n");

         else

             printf("Good job,rabbit!\n");

     }

     return ;

 }

代码君

相关文章