ZOJ2972 Hurdles of 110m(dp)

题目链接。

分析：

这题是几周前比赛时没有做出来的一道。说来惭愧，比完赛，翻翻解题报告也没看懂，就把这题放下了。今天闲来没事，做了做，一遍AC。

果然应了那句古话，岁月不饶人（题）啊。

设dp[i][j]表示第i个阶段j能量所耗费的时间

状态转移方程：

dp[i][j] = min(dp[i][j], dp[i-1][j-F1]+T1)　　  (Fast Mode)

dp[i][j] = min(dp[i][j], dp[i-1][j]+T2) 　　　　(Normal Mode)

dp[i][j] = min(dp[i][j], dp[i-1][j+F2]+T3) 　　(Slow Mode)

AC代码如下：

#include <stdio.h>

const int INF = (1<<24);

#define MAXN 120

#define min(x,y) ((x)<(y)?(x):(y))

int dp[MAXN][MAXN];

int main(){
    int i, j, n, t1, t2, t3, f1, f2, T, m, k, min_cost;
    scanf("%d", &T);
    while(T--){
        scanf("%d %d", &n, &m);
        for(i=0; i<=n; i++){
            for(j=0; j<=m; j++){
                dp[i][j] = INF;
            }
        }
        dp[0][m] = 0;
        for(i=1; i<=n; i++){
            scanf("%d %d %d %d %d", &t1, &t2, &t3, &f1, &f2);
            for(j=0; j<=m; j++){
                k = j - f1;
                if(k>=0) dp[i][k] = min(dp[i][k], dp[i-1][j]+t1);
                k = j;
                dp[i][k] = min(dp[i][k], dp[i-1][j]+t2);
                k = j+f2;
                if(k>m) k = m;
                dp[i][k] = min(dp[i][k], dp[i-1][j]+t3);
            }
        }
        min_cost = INF;
        for(i=0; i<=m; i++){
            if(dp[n][i] < min_cost) min_cost = dp[n][i];
        }

        printf("%d\n", min_cost);
    }

    return 0;
}