跑跑卡丁車

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1778????Accepted Submission(s): 583


Problem Description跑跑卡丁車是時下一款流行的網(wǎng)絡(luò)休閑游戲，你可以在這虛擬的世界里體驗駕駛的樂趣。這款游戲的特別之處是你可以通過漂移來獲得一種
加速卡，用這種加速卡可以在有限的時間里提高你的速度。為了使問題簡單化，我們假設(shè)一個賽道分為L段，并且給你通過每段賽道的普通耗時Ai和用加速卡的耗時Bi。加速卡的獲得機制是：普通行駛的情況下，每通過1段賽道,可以獲得20%的能量(N2O).能量集滿后獲得一個加速卡(同時能量清0).加速卡最多可以儲存2個,也就是說當(dāng)你有2個加速卡而能量再次集滿,那么能量清零但得不到加速卡。一個加速卡只能維持一段賽道，游戲開始時沒有加速卡。




問題是，跑完n圈最少用時為多少？
Input每組輸入數(shù)據(jù)有3行，第一行有2個整數(shù)L(0<L<100),N(0<N<100)分別表示一圈賽道分為L段和有N圈賽道，接下來兩行分別有L個整數(shù)Ai和Bi
(Ai > Bi).

Output對于每組輸入數(shù)據(jù)，輸出一個整數(shù)表示最少的用時.

Sample Input18 1
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
8 8 8 8 8 8 8 8 8 8 8 8 8 8 1 1 8 8
Sample Output145HintHint 對于sample這組數(shù)據(jù)，你可以先在普通情況下行駛前14段，這時你有2個加速卡以及80%的能量(N2O).在第15和16段用掉2個加速卡，通過第17段賽道后又可以得到一個加速卡，在第18段賽道使用.
Authorxhd
Source“2006校園文化活動月”之“校慶杯”大學(xué)生程序設(shè)計競賽暨杭州電子科技大學(xué)第四屆大學(xué)生程序設(shè)計競賽
RecommendLL

#include <iostream>#include <cstring>#include <cstdio>
using namespace std;
int a[11111],b[11111];int dp[11111][15];
const int INF=0x3f3f3f3f;
int main(){int L,N;while(cin>>L>>N){int tot=L*N;
for(int i=0;i<L;i++)cin>>a;for(int i=0;i<L;i++)cin>>b;
for(int i=0;i<=tot;i++){a=a[i%L];b=b[i%L];}
for(int i=0;i<=tot+10;i++)for(int j=0;j<=15;j++)dp[j]=INF;dp[0][0]=0;dp[1][1]=a[0];
for(int i=1;i<tot;i++){for(int j=0;j<15;j++){int k=j+1;if(k==15) ?k=10;dp[i+1][k]=min(dp[j]+a,dp[i+1][k]);if(j-5>=0)dp[i+1][j-5]=min(dp[j]+b,dp[i+1][j-5]);}}/*for(int i=0;i<15;i++)cout<<dp[tot]<<" ";cout<<endl;*/int ans=INF;for(int i=0;i<15;i++)ans=min(ans,dp[tot]);
cout<<ans<<endl;}
return 0;}

轉(zhuǎn)載于:https://www.cnblogs.com/CKboss/archive/2013/06/11/3351022.html

總結(jié)

以上是生活随笔為你收集整理的HDOJ 1494 跑跑卡丁车的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。