hdu2059: http://acm.hdu.edu.cn/showproblem.php?pid=2059
題意：烏龜騎著充滿電的電動車從起點出發，途中有n個充電站，離起點的距離為p[i]，電動車每次充電后電動時間為t，烏龜電動速度為v1，腳踩電動車速度為v2，兔子恒速為vr，問龜兔輸贏。 解法：dp:優化前方程：dp[i][j]表示烏龜上次充電的站點為j,為從起點到i站時間，dp[i][j]=min(dp[i][j],x+dp[j][k]),dp[j][k]為在站點k充電后到j，從起點到j站花費的最短時間（最短因為已經算過了），x為從j站到i站花費的時間，需要3個for。可優化為一維，dp[i]表示從某個站點充電后到達i所用的最短時間，則dp[i]=min(dp[i],dp[j]+x),只需2個for。 優化前code: #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; const int inf=1<<30; double dp[150][150]; int p[150]; int min(int a,int b) {if(a<b)return a;elsereturn b; } int main() {int l,n,c,t,vr,v1,v2;double x,mm;while(scanf("%d",&l)!=EOF){scanf("%d%d%d",&n,&c,&t);scanf("%d%d%d",&vr,&v1,&v2);for(int i=1;i<=n;i++)scanf("%d",&p[i]);for(int i=0;i<=n+1;i++)for(int j=0;j<=n+1;j++)dp[i][j]=inf;p[n+1]=l;p[0]=0;dp[0][0]=0;for(int i=1;i<=n+1;i++){if(p[i]<c)dp[i][0]=1.0*p[i]/v1;else dp[i][0]=1.0*c/v1+1.0*(p[i]-c)/v2;}for(int i=1;i<=n+1;i++) //枚舉末站點 {for(int j=0;j<i;j++) //枚舉初站點 {if(p[i]-p[j]<c)x=t+1.0*(p[i]-p[j])/v1;elsex=t+1.0*c/v1+1.0*(p[i]-p[j]-c)/v2; //求出從j到i的時間for(int k=0;k<j;k++)dp[i][j]=min(dp[i][j],x+dp[j][k]); }}mm=dp[n+1][0];for(int i=1;i<=n+1;i++)if(dp[n+1][i]<mm)mm=dp[n+1][i];if(mm<1.0*l/vr)printf("What a pity rabbit!\n");elseprintf("Good job,rabbit!\n");} } 優化后code: #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; double dp[150]; int p[150]; int min(int a,int b) {if(a<b)return a;elsereturn b; } int main() {int l,n,c,t,vr,v1,v2;double x;while(scanf("%d",&l)!=EOF){scanf("%d%d%d",&n,&c,&t);scanf("%d%d%d",&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+1;i++){if(p[i]<c)dp[i]=1.0*p[i]/v1;else dp[i]=1.0*c/v1+1.0*(p[i]-c)/v2;}for(int i=1;i<=n+1;i++){for(int j=0;j<i;j++){if(p[i]-p[j]<c)x=t+1.0*(p[i]-p[j])/v1;elsex=t+1.0*c/v1+1.0*(p[i]-p[j]-c)/v2;dp[i]=min(dp[i],dp[j]+x);}}if(dp[n+1]<1.0*l/vr)printf("What a pity rabbit!\n");elseprintf("Good job,rabbit!\n");} } /*input: 100 3 20 5 5 8 2 10 40 60 100 3 60 5 5 8 2 10 40 60 output: Good job,rabbit! What a pity rabbit! */

轉載于:https://www.cnblogs.com/acmjun/archive/2012/07/25/2608194.html

總結

以上是生活随笔為你收集整理的hdu2059:龟兔赛跑的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。