POJ 1661 暴力dp

绝地灬酷狼 2023-08-17 16:37 131阅读 0赞

题意略。

思路：

很有意思的一个题，我采用的是主动更新未知点的方式，也即刷表法来dp。

我们可以把整个路径划分成横向移动和纵向移动，题目一开始就给出了Jimmy的高度，这就是纵向移动的距离。

我们dp的目标是每个线段端点的横向移动最小值。

有一个小trick，就是有可能Jimmy开始就可以落在地上，没有必要或者说在下落过程中不会有间隔来阻拦。

代码附上：

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 1005;
    const int INF = 0x3f3f3f3f;
    const int F = 0x3f;
    
    struct segment{
        int l,r,h;
        segment(int l = 0,int r = 0,int h = 0){
            this->l = l,this->r = r,this->h = h;
        }
    };
    
    segment store[maxn];
    int dp[maxn<<1],N,x,h,MAX,t;
    bool covered[maxn<<1];
    
    bool cmp(const segment& s0,const segment& s1){
        return s0.h > s1.h;
    }
    bool inSegment(int x,segment s){
        return s.l <= x && x <= s.r;
    }
    
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d%d%d",&N,&x,&h,&MAX);
            for(int i = 0;i < N;++i) scanf("%d%d%d",&store[i].l,&store[i].r,&store[i].h);
            memset(dp,F,sizeof(dp));
            memset(covered,false,sizeof(covered));
            sort(store,store + N,cmp);
            int ans = h,lft,rht,lp,rp,nlft,nrht,nlp,nrp;
            for(int i = 0;i < N;++i){
                lft = i<<1,rht = lft + 1;
                if(inSegment(x,store[i])){
                    dp[lft] = x - store[i].l,dp[rht] = store[i].r - x;
                    break;
                }
            }
            for(int i = 0;i < N;++i){
                lft = i<<1,rht = lft + 1;
                lp = store[i].l,rp = store[i].r;
                int cnt0 = 0,cnt1 = 0;
                if(dp[lft] == INF) continue;
                for(int j = i + 1;store[i].h - store[j].h <= MAX && j < N && cnt0 + cnt1 < 2;++j){
                    if(store[i].h == store[j].h) continue;
                    nlft = j<<1,nrht = nlft + 1;
                    nlp = store[j].l,nrp = store[j].r;
                    if(!cnt0 && inSegment(lp,store[j])){
                        dp[nlft] = min(dp[nlft],dp[lft] + lp - nlp);
                        dp[nrht] = min(dp[nrht],dp[lft] + nrp - lp);
                        cnt0 = 1;
                    }
                    if(!cnt1 && inSegment(rp,store[j])){
                        dp[nlft] = min(dp[nlft],dp[rht] + rp - nlp);
                        dp[nrht] = min(dp[nrht],dp[rht] + nrp - rp);
                        cnt1 = 1;
                    }
                }
            }
            
            
            for(int i = 0;i < N;++i){
                if(store[i].h > MAX) continue;
                for(int j = i + 1;j < N;++j){
                    if(inSegment(store[i].l,store[j])) covered[i<<1] = true;
                    if(inSegment(store[i].r,store[j])) covered[i<<1 | 1] = true;
                }
            }
            
            int minn = INF;
            for(int i = N - 1;i >= 0 && store[i].h <= MAX;--i){
                lft = i<<1,rht = lft + 1;
                if(!covered[lft]) minn = min(minn,dp[lft]);
                if(!covered[rht]) minn = min(minn,dp[rht]);
            }
            if(minn == INF) minn = 0;
            ans += minn;
            printf("%d\n",ans);
        }
        return 0;
    }
    
    /*
    
    1
    3 4 4 5
    3 5 3
    1 7 2
    2 6 1
    */

转载于:https://www.cnblogs.com/tiberius/p/11259537.html