首页 > 代码库 > hdu1494 跑跑卡丁车 (动态规划)
hdu1494 跑跑卡丁车 (动态规划)
Problem Description
http://acm.hdu.edu.cn/showproblem.php?pid=1494
跑跑卡丁车是时下一款流行的网络休闲游戏,你可以在这虚拟的世界里体验驾驶的乐趣。这款游戏的特别之处是你可以通过漂移来获得一种
加速卡,用这种加速卡可以在有限的时间里提高你的速度。为了使问题简单化,我们假设一个赛道分为L段,并且给你通过每段赛道的普通耗时Ai和用加速卡的耗时Bi。加速卡的获得机制是:普通行驶的情况下,每通过1段赛道,可以获得20%的能量(N2O).能量集满后获得一个加速卡(同时能量清0).加速卡最多可以储存2个,也就是说当你有2个加速卡而能量再次集满,那么能量清零但得不到加速卡。一个加速卡只能维持一段赛道,游戏开始时没有加速卡。
问题是,跑完n圈最少用时为多少?
加速卡,用这种加速卡可以在有限的时间里提高你的速度。为了使问题简单化,我们假设一个赛道分为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).
(Ai > Bi).
Output
对于每组输入数据,输出一个整数表示最少的用时.
Sample Input
18 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 Output
145题目分析:动态规划问题,我感觉做这个题的时候,不要纠结时间的问题,不要管未来还是过去,计算机是处理问题的,能找到最优就好,此题的解释在代码中有详细的注释。AC代码:/** *@xiaoran *DP; *可以用dp[i]表示在第i段的最小时间,可以用j表示能量槽的个数,最多15个状态 *dp[i][j]:在第i段时的第j个能量槽满的状态下的最小时间,可以肯定最先时间为 *dp[n][k]:n表示圈数,k=[1,14],到达15段的时候会自动清零,也不会得到能量 *dp[i][j]=min(dp[i][j],dp[i-1][j-1]+a[i],dp[i-1][j+5]+b[i]) *注释:dp[i][j]可以通过dp[i-1][j-1]不使用加速卡直接行使得到, * :dp[i][j]可以通过使用加速卡直接行使得到,使用加速了会减少5个能量槽, * 相当于用了以后的5个能量槽,dp时候不应该一直纠结时间的状态,超前或延后 * 特别,在j==10的时候可以通过dp[i-1][14]得到,因为此时已经2个加速卡,当集满 * 五个能量槽的时候只是会清零 *对于n圈可以表示成n*l段 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long #define inf 0x3f3f3f3f using namespace std; int a[10010],b[10010],dp[10010][16]; int main() { int l,n; while(scanf("%d%d",&l,&n)==2){ for(int i=1;i<=l;i++){ scanf("%d",&a[i]); for(int j=1;j<=n;j++){ a[i+j*l]=a[i]; } } for(int i=1;i<=l;i++){ scanf("%d",&b[i]); for(int j=1;j<=n;j++){ b[i+j*l]=b[i]; } } memset(dp,inf,sizeof(dp));//求的是最小值,初始化为相对大的值 dp[0][0]=0; for(int i=1;i<=l*n;i++){ for(int j=0;j<15;j++){ if(j!=0) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+a[i]); if(j<10) dp[i][j]=min(dp[i][j],dp[i-1][j+5]+b[i]); if(j==10) dp[i][j]=min(dp[i][j],dp[i-1][14]+a[i]); } } int res=dp[l*n][0]; for(int i=0;i<15;i++){ if(res>dp[l*n][i]){ res=dp[l*n][i]; } } printf("%d\n",res); } return 0; }
hdu1494 跑跑卡丁车 (动态规划)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。