ZOJ 2972 Hurdles of 110m 【DP 背包】

Dear 丶 2021-12-10 16:45 252阅读 0赞

一共有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-7      ;
    const int N = 22             ;
    const int M = 1100011*2      ;
    const ll P = 10000000097ll   ;
    const int MAXN = 100000      ;
    const int INF = 0x3f3f3f3f   ;
    const int MAX = 10500        ;
    
    struct sc{
        int t1, t2, t3, f1, f2;
    }a[120];
    
    int n, m;
    int dp[120][120];
    
    int main(){
        std::ios::sync_with_stdio(false);
        int i, j, t, k, l, u, v, x, y, numCase = 0;
        cin >> t;
        while(t--){
            cin >> n >> m;
            for(i = 0; 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[0][m] = 0;
            for(i = 0; i < n; ++i){
                for(j = 0; j <= m; ++j){
                    if(j >= a[i].f1){
                        checkmin(dp[i + 1][j - a[i].f1], dp[i][j] + a[i].t1);
                    }
                    if(j + a[i].f2 > m){
                        checkmin(dp[i + 1][m], dp[i][j] + a[i].t3);
                    } else{
                        checkmin(dp[i + 1][j + a[i].f2], dp[i][j] + a[i].t3);
                    }
                    checkmin(dp[i + 1][j], dp[i][j] + a[i].t2);
                }
            }
            int ans = INF;
            for(i = 0; i <= m; ++i){
                checkmin(ans, dp[n][i]);
            }
            cout << ans << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/wushuaiyi/p/4326250.html