POJ - 1661 - Help Jimmy - 简单dp

时间：2022-06-13 23:57:34

http://poj.org/problem?id=1661

一般化处理，把一开始的落地和大地都视作平台，设计平台类的属性。dp的时候显然是从上往下dp的，而且要小心Jimmy不能够穿过平台，也就是从平台左侧掉下或者从右侧掉下都只能有一次。

#include<cmath>

#include<algorithm>

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

int N,X,Y,MAX;

struct P{

    int lx,rx,y;

    int lt,rt;

    int t;

    bool operator<(P that){

        return y>that.y;

    }

}p[];

void update(int id){

    int leftblock=;

    int rightblock=;

    for(int i=id+;i<N+;i++){

        int dh=p[id].y-p[i].y;

        if(dh>MAX)

            return;

        if(leftblock==&&p[i].lx<=p[id].lx&&p[i].rx>=p[id].lx){

            p[i].lt=min(p[i].lt,p[id].lt+dh+abs(p[id].lx-p[i].lx));

            p[i].rt=min(p[i].rt,p[id].lt+dh+abs(p[id].lx-p[i].rx));

            p[i].t=min(p[i].t,p[id].lt+dh);

            leftblock=;

        }

        if(rightblock==&&p[i].lx<=p[id].rx&&p[i].rx>=p[id].rx){

            p[i].lt=min(p[i].lt,p[id].rt+dh+abs(p[id].rx-p[i].lx));

            p[i].rt=min(p[i].rt,p[id].rt+dh+abs(p[id].rx-p[i].rx));

            p[i].t=min(p[i].t,p[id].rt+dh);

            rightblock=;

        }

        //cout<<"i="<<i<<" "<<p[i].lt<<" "<<p[i].rt<<" "<<p[i].t<<endl;

    }

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d%d",&N,&X,&Y,&MAX);

        p[].lx=p[].rx=X;

        p[].y=Y;

        p[].lt=p[].rt=p[].t=;

        for(int i=;i<N+;i++){

            scanf("%d%d%d",&p[i].lx,&p[i].rx,&p[i].y);

            p[i].lt=p[i].rt=p[i].t=0x3f3f3f3f;

        }

        p[N+].lx=-;

        p[N+].rx=;

        p[N+].y=;

        p[N+].lt=p[N+].rt=p[N+].t=0x3f3f3f3f;

        sort(p,p+N+);

        for(int i=;i<N+;i++){

            update(i);

            //cout<<p[i].lt<<" "<<p[i].rt<<" "<<p[i].t<<endl;

        }

        printf("%d\n",p[N+].t);

    }

}

2月24日就整理到这里了

相关文章