ZOJ 2972 Hurdles of 110m 【DP 背包】

一共有N段过程，每段过程里可以选择 快速跑、 匀速跑 和 慢速跑

对于快速跑会消耗F1 的能量， 慢速跑会集聚F2的能量

选手一开始有M的能量，即能量上限

求通过全程的最短时间

定义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)

Source Code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

#include <stack>

#include <string>

#include <map>

#include <set>

#include <list>

#include <queue>

#include <vector>

#include <algorithm>

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

#define pi acos(-1.0)

using namespace std;

typedef long long           ll      ;

typedef unsigned long long  ull     ;

typedef unsigned int        uint    ;

typedef unsigned char       uchar   ;

template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}

template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}

const double eps = 1e-      ;

const int N =              ;

const int M = *      ;

const ll P = 10000000097ll   ;

const int MAXN =       ;

const int INF = 0x3f3f3f3f   ;

const int MAX =         ;

struct sc{

    int t1, t2, t3, f1, f2;

}a[];

int n, m;

int dp[][];

int main(){

    std::ios::sync_with_stdio(false);

    int i, j, t, k, l, u, v, x, y, numCase = ;

    cin >> t;

    while(t--){

        cin >> n >> m;

        for(i = ; i < n; ++i){

            cin >> a[i].t1 >> a[i].t2 >> a[i].t3 >> a[i].f1 >> a[i].f2;

        }

        memset(dp, 0x3f, sizeof(dp));

        dp[][m] = ;

        for(i = ; i < n; ++i){

            for(j = ; j <= m; ++j){

                if(j >= a[i].f1){

                    checkmin(dp[i + ][j - a[i].f1], dp[i][j] + a[i].t1);

                }

                if(j + a[i].f2 > m){

                    checkmin(dp[i + ][m], dp[i][j] + a[i].t3);

                } else{

                    checkmin(dp[i + ][j + a[i].f2], dp[i][j] + a[i].t3);

                }

                checkmin(dp[i + ][j], dp[i][j] + a[i].t2);

            }

        }

        int ans = INF;

        for(i = ; i <= m; ++i){

            checkmin(ans, dp[n][i]);

        }

        cout << ans << endl;

    }

    return ;

}