#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int L,N,C,T,p[110]; int vr,v1,v2; double dp[110]; int main(){ while(cin>>L && L) { cin>>N>>C>>T; cin>>vr>>v1>>v2; for(int i=1;i<=N;i++){ scanf("%d",&p[i]); } p[N+1]=L; p[0]=0; dp[0]=0; for(int i=1;i<N+2;i++){//从第一个开始,依次枚举每一个点 dp[i]=(0xfffffff); for(int j=0;j<i;j++){//枚举到达i 之前的最后一次充电位置,求出dp[i] int tmp=p[i]-p[j]; double tmp2=(tmp>C? C*1.0/v1+(tmp-C+0.0)/v2:tmp*1.0/v1); tmp2+=dp[j]; if(j) tmp2+=T; dp[i]=min(dp[i],tmp2); } } dp[N+1]>L*1.0/vr? printf("Good job,rabbit!\n"):printf("What a pity rabbit!\n"); } return 0; }
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2059
唉,这题真的是把我给搞醉了!!!
看了别人的代码,基本能理解了,可是几乎是一样的代码,可我的就是有问题,TMD找了N久也没有找到错误,太蛋疼了,后面终于找到错误了:我把 double 用scanf 输入时用成%d了!!!想到这里就是泪啊啊啊啊啊。。。
思路:按加油地点数量进行枚举,得一个for循环,用dp[i]表示从第一个到第i个供电站的最小时间,则不进行优化的话,那么,到达i之前的最后一次充电可能是在0——j(j<i)之间的任何一个,那么我们只要再枚举i之前的任何一个位置,选取最小的值作为dp[i]的值即可。
所以可以得到类似于最长上升序列的递推形式:dp[i]=min(dp[i],dp[j]+(从j到达i所需的时间,这段时间没有再充电)),dp[i]初始化为Max;