1-10假期训练（hdu-2059 简单dp）

题目一：传送门

思路：水题，模拟即可

题目二：传送门

思路：dp，决策每个充电站是否要充电。（决策只有搜索，DP两种解决方法）

（1）考虑状态的个数，n+2个，因为除了n个还有位置0，终点len两种状态；

前一个状态可以推出后一个状态，所以可以得到循环的顺序外循环1--n，内循环i-1--0。

（2）状态转移方程：dp[i]=MIN(dp[i],dp[i]+x,dp[i]+y)，x表示要充电，y表示不要充电。

（3）考虑x和y的求法：

如果j==0，只考虑x即可，因为第一次肯定充满电

如果j！=0，考虑x，y分为dis(i-j)>=c和dis(i-j)<c两种情况，分别计算就行（一开始就是这里被卡住了，

如果dis(i-j)>c只要将它分为两部分考虑，分别计算v1的速度耗时和v2速度耗时即可）。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 120;
double MIN(double a,double b)
{
    return a<b?a:b;
}
double dp[maxn],l[maxn]; //记录每次的时间，为浮点型。 
int main(void)
{
    double x,y,timtu,num,num2;
    int len; //初始题中的变量均为整形，n个位置除外 
    int n,c,t;
    int v,v1,v2;
    int i,j; 
    while(~scanf("%d",&len))
    {
        scanf("%d%d%d",&n,&c,&t);
        scanf("%d%d%d",&v,&v1,&v2);
        for(i=1;i<=n;i++) scanf("%lf",&l[i]);
        l[0]=0;l[n+1]=len;
        for(i=1;i<maxn;i++) dp[i]=INT_MAX;dp[0]=0; //初始化处理dp，比较min，所以初始化最大 
        timtu=len*1.0/v;
        for(i=1;i<=n+1;i++)
        {
            for(j=i-1;j>=0;j--)
            {
                if(j==0) //特殊情况 
                {
                    num=l[i]-l[0];
                    if(num<=c) dp[i]=MIN(dp[i],dp[0]+1.0*num/v1);
                    else
                    {
                        num2=1.0*c/v1;
                        num-=c;
                        num2+=1.0*num/v2;
                        dp[i]=MIN(dp[i],dp[0]+num2);
                    }
                }
                else
                {
                    x=t;num=l[i]-l[j];y=1.0*num/v2; //x表示需要充电，y表示不用充电。 
                    if(num<=c) x+=num*1.0/v1;
                    else
                    {
                        x+=c*1.0/v1;
                        num-=c;
                        x+=num*1.0/v2;
                    }
                    dp[i]=MIN(dp[i],dp[j]+MIN(x,y));
                }
            }
        }
        if(dp[n+1]>=timtu) printf("Good job,rabbit!
");
        else printf("What a pity rabbit!
");
    }
    return 0;
}