M - Help Jimmy POJ - 1661 ——dp

青旅半醒 2022-06-10 05:46 77阅读 0赞

Think:  
1知识点：dp  
2动态转移方程

dp[i][0]:表示从第i个木板左端点跳跃的当前最优解
    dp[i][1]:表示从第i个木板右端点跳跃的当前最优解

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    struct Node{
        int x1, x2;
        int h;
        bool operator < (const Node &b) const {
            return h < b.h;
        }
    }node[1014];
    
    int H, dp[1014][2];
    /*
    dp[i][0]:表示从第i个木板左端点跳跃的当前最优解
    dp[i][1]:表示从第i个木板右端点跳跃的当前最优解
    */
    
    void left_time(int z, int n);
    void right_time(int z, int n);
    void ans_time(int n);
    
    int main(){
        int T, i, n, x, y;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d %d %d", &n, &x, &y, &H);
            node[n+1].x1 = node[n+1].x2 = x, node[n+1].h = y;
            node[0].x1 = -20000, node[0].x2 = 20000, node[0].h = 0;
            for(i = 1; i <= n; i++)
                scanf("%d %d %d", &node[i].x1, &node[i].x2, &node[i].h);
            sort(node, node+n+2);
            ans_time(n);
        }
        return 0;
    }
    void left_time(int z, int n){
       /*第z个左端点跳跃*/
        for(int i = z-1; i > 0; i--){
       /*注意i的范围:[1, z-1]*/
            int dh = node[z].h - node[i].h;
            if(dh <= H && node[i].x1 <= node[z].x1 && node[i].x2 >= node[z].x1){
       /*判断是否满足直接落在木板上的条件*/
                int u = node[z].x1 - node[i].x1;
                int v = node[i].x2 - node[z].x1;
                dp[z][0] = dh + min(dp[i][0]+u, dp[i][1]+v);
                return;/*已经直接落在木板上*/
            }
        }
        if(node[z].h <= H)/*判断是否可直接跳到地面上*/
            dp[z][0] = node[z].h;
        else
            dp[z][0] = inf;
    }
    void right_time(int z, int n){
       /*第z个右端点跳跃*/
        for(int i = z-1; i > 0; i--){
       /*注意i的范围:[1, z-1]*/
            int dh = node[z].h - node[i].h;
            if(dh <= H && node[i].x1 <= node[z].x2 && node[i].x2 >= node[z].x2){
       /*判断是否满足直接落在木板上的条件*/
                int u = node[z].x2 - node[i].x1;
                int v = node[i].x2 - node[z].x2;
                dp[z][1] = dh + min(dp[i][0]+u, dp[i][1]+v);
                return;/*已经直接落在木板上*/
            }
        }
        if(node[z].h <= H)/*判断是否可直接跳到地面上*/
            dp[z][1] = node[z].h;
        else
            dp[z][1] = inf;
    }
    void ans_time(int n){
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n+1; i++){
            left_time(i, n);/*试探左端点跳跃的最短时间*/
            right_time(i, n);/*试探右端点跳跃的最短时间*/
        }
        printf("%d\n", min(dp[n+1][0], dp[n+1][1]));
    }

[vjudge]: https://vjudge.net/contest/163018#problem/M