跑跑卡丁车Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2514Accepted Submission(s): 875
Problem Description
跑跑卡丁车是时下一款流行的网络休闲游戏，你可以在这虚拟的世界里体验驾驶的乐趣。这款游戏的特别之处是你可以通过漂移来获得一种加速卡，用这种加速卡可以在有限的时间里提高你的速度。为了使问题简单化，我们假设一个赛道分为L段，并且给你通过每段赛道的普通耗时Ai和用加速卡的耗时Bi。加速卡的获得机制是：普通行驶的情况下，每通过1段赛道,可以获得20%的能量(N2O).能量集满后获得一个加速卡(同时能量清0).加速卡最多可以储存2个,也就是说当你有2个加速卡而能量再次集满,那么能量清零但得不到加速卡。一个加速卡只能维持一段赛道，游戏开始时没有加速卡。
问题是，跑完n圈最少用时为多少？
Input
每组输入数据有3行，第一行有2个整数L(0<L<100),N(0<N<100)分别表示一圈赛道分为L段和有N圈赛道，接下来两行分别有L个整数Ai和Bi(Ai > Bi).
Output
对于每组输入数据，输出一个整数表示最少的用时.
Sample Input
18 19 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 98 8 8 8 8 8 8 8 8 8 8 8 8 8 1 1 8 8
Sample Output
145
Hint
Hint
对于sample这组数据，你可以先在普通情况下行驶前14段，这时你有2个加速卡以及80%的能量(N2O).在第15和16段用掉2个加速卡，通过第17段赛道后又可以得到一个加速卡，，在第18段赛道使用.
一道dp题目。
注释里是第一次打的代码，用了二维来记录状态。
后来看了题解，就把time 一维 用来 做滚动数组。 然后把20%NO记做1。一张卡 记做5。这样只用一维，比较简单。
按要求写出状态方程。
加速的时候time[cur][k]=min(time[cur][k],time[cur^1][k+5]+b[j]);
不加速的时候time[cur][k]=min(time[cur][k],time[cur^1][k-1]+a[j]);
注意，如果两张卡，而且有80%的NO的时候 再积累NO， 那么不会多得到一张卡片。 time[cur][10]=min(time[cur][10],time[cur^1][14]+a[j]);
#include <stdio.h> #include <iostream>#include <algorithm>#include <cmath>#include <map>#include <string>using namespace std;int time[2][20]; //一维滚动数组 int a[110],b[110];int main(){int L,n;while(scanf("%d%d",&L,&n)!=EOF){for(int i=0;i<=14;i++){time[0][i]=99999999; }time[0][0]=0;for(int i=0;i<L;i++)cin>>a[i];for(int i=0;i<L;i++)cin>>b[i]; int cur=0; for(int i=0;i<n;i++){for(int j=0;j<L;j++){cur^=1;for(int k=0;k<=14;k++)time[cur][k]=99999999;/*for(int k=0;k<=14;k++){if(k%5==0)puts("");printf("%9d",time[cur^1][k]);}puts("\n");*/for(int k=0;k<=14;k++){//加速 bif(k<=9)time[cur][k]=min(time[cur][k],time[cur^1][k+5]+b[j]);//普通 aif(k!=0)time[cur][k]=min(time[cur][k],time[cur^1][k-1]+a[j]);//if(k==10)//time[cur][10]=min(time[cur][10],time[cur^1][14]+a[j]);}}} int minn=99999999;for(int i=0;i<=14;i++)minn=min(minn,time[cur][i]);printf("%d\n",minn);}return 0;}/*int time[2][5][10];//一维滚动数组 二维记录有几张卡 三维记录当前有多少NOint a[110],b[110];//耗时间int main(){int L,n;while(scanf("%d%d",&L,&n)!=EOF){for(int i=0;i<3;i++){for(int j=0;j<5;j++){time[0][i][j]=99999999;}}time[0][0][0]=0;for(int i=0;i<L;i++){scanf("%d",a+i);}for(int i=0;i<L;i++){scanf("%d",b+i);}int cur=0;for(int i=0;i<n;i++)//quan{for(int j=0;j<L;j++)//duan{cur^=1;//当前的for(int k=0;k<3;k++){for(int l=0;l<5;l++){//printf("%8d ",time[cur^1][k][l]);time[cur][k][l]=99999999;}//puts("");}//puts("");//用卡加速的情况 //bfor(int k=0;k<2;k++){for(int l=0;l<5;l++){time[cur][k][l]=min(time[cur][k][l],time[cur^1][k+1][l]+b[j]);}}//不用卡的情况 //afor(int k=0;k<3;k++){for(int l=0;l<5;l++){if(l!=0)//增加 NOtime[cur][k][l]=min(time[cur][k][l],time[cur^1][k][l-1]+a[j]);else if(k!=0)//{time[cur][k][l]=min(time[cur][k][l],time[cur^1][k-1][4]+a[j]);//增加卡片if(k==2)//卡片 超过2 不增加卡片time[cur][k][l]=min(time[cur][k][l],time[cur^1][k][4]+a[j]);}}}}}int ans=99999999;for(int k=0;k<3;k++){for(int l=0;l<5;l++){ans=min(ans,time[cur][k][l]);}}printf("%d\n",ans); }return 0;}*//*18 19 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 98 8 8 8 8 8 8 8 8 8 8 8 8 8 1 1 8 8*/
我是在旅行吗？也许是的。
