首页 > ACM题库 > HDU-杭电 > HDU 1494 跑跑卡丁车-动态规划-[解题报告] C++
2013
12-11

HDU 1494 跑跑卡丁车-动态规划-[解题报告] C++

跑跑卡丁车

问题描述 :

跑跑卡丁车是时下一款流行的网络休闲游戏,你可以在这虚拟的世界里体验驾驶的乐趣。这款游戏的特别之处是你可以通过漂移来获得一种
加速卡,用这种加速卡可以在有限的时间里提高你的速度。为了使问题简单化,我们假设一个赛道分为L段,并且给你通过每段赛道的普通耗时Ai和用加速卡的耗时Bi。加速卡的获得机制是:普通行驶的情况下,每通过1段赛道,可以获得20%的能量(N2O).能量集满后获得一个加速卡(同时能量清0).加速卡最多可以储存2个,也就是说当你有2个加速卡而能量再次集满,那么能量清零但得不到加速卡。一个加速卡只能维持一段赛道,游戏开始时没有加速卡。

问题是,跑完n圈最少用时为多少?

输入:

每组输入数据有3行,第一行有2个整数L(0<L<100),N(0<N<100)分别表示一圈赛道分为L段和有N圈赛道,接下来两行分别有L个整数Ai和Bi
(Ai > Bi).

输出:

对于每组输入数据,输出一个整数表示最少的用时.

样例输入:

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

样例输出:

145

Hint
Hint
对于sample这组数据,你可以先在普通情况下行驶前14段,这时你有2个加速卡以及80%的能量(N2O).在第15和16段用掉2个加速卡,通过第 17段赛道后又可以得到一个加速卡,在第18段赛道使用.

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1494

题目大意:根据跑跑卡丁车改造而来的动态规划题目。跑道中每圈都分n个赛道,有L圈,跑完一个赛道能量加%20,跑完5个赛道能量满送一个加速卡,最多2个加速卡,如果加速卡为2个,能量为%100,又从0开始,不送加速卡。题目给定n个数ai和bi,ai为每个赛道正常耗时,bi为加速时的耗时。问最少需要多少时间?

解题思路:刚看到这题没什么思路,后来把这题转化为背包模型,每个%20能量算一个单位,最多有15个,如果大于5个有一个加速卡,如果大于10个有2个加速卡,如果等于16则边为10,2个满时清0.15就是背包的最多容量,正常跑算一个物品,权值(这里不说重量有负值)为1,价值为ai,加速也算一个物品,权值为-5,价值为bi,每次都必须选一个物品,问最后获得得最少价值。恩,有点牵强,但只要转化好理解些。

    那么状态转移方程为:dp[i+1][j+1] = min(dp[i][j]+a[i],dp[i+1][j+1]);  (dp[i][j]表示跑了i个赛道能量为j时最少的耗时,a[i]为正常跑的时间,和背包的转移方程很像吧)

                                        dp[i+1][j-5] = min(dp[i][j]+b[i],dp[i+1][j-5);

测试数据:

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


代码:

#include <stdio.h>
#include <string.h>
#define MAX 10010
#define INF 1000000000
#define MIN(a,b) (a)<(b)?(a):(b)


int n,m,tot,dp[MAX][16];
int A[MAX],B[MAX];


int main()
{
    int i,j,k,t,add,next;


    while (scanf("%d%d",&n,&m) != EOF) {

        tot = n * m;
        for (i = 0; i < n; ++i)
            scanf("%d",&A[i]);
        for (j = 0; j < n; ++j)
            scanf("%d",&B[j]);
        for (i = 0; i < tot; ++i)
            A[i] = A[i%n],B[i] = B[i%n];
        
        
        for (i = 0; i <= 15; ++i)
            for (j = 0; j <= tot; ++j)
                dp[j][i] = INF;
        dp[1][1] = A[0];
        
        
        for (i = 1; i < tot; ++i)
            for (j = 0; j < 15; ++j) {

                k = j + 1;
                if (k == 15) k = 10;
                dp[i+1][k] = MIN(dp[i][j]+A[i],dp[i+1][k]);
                if (j >= 5) dp[i+1][j-5] = MIN(dp[i][j]+B[i],dp[i+1][j-5]);
            }


        int ans = INF;
        for (i = 0; i < 15; ++i)
            ans = MIN(ans,dp[tot][i]);
        printf("%d\n",ans);
    }
}

本文ZeroClock原创,但可以转载,因为我们是兄弟。

解题报告转自:http://blog.csdn.net/woshi250hua/article/details/7606556


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的