POJ1661Help Jimmy _dp

将题目模型想象成水流的下落：遇到木板后分成两股水流继续向下，问什么时候能到达地面（假设地面是最后一个木板）

 

dp[i][0] 水流到达第i个木板左端点的最早时间 

dp[i][1] 右端点

 

[cpp]  

//poj1661  

#include<iostream>  

#include<cstdio>  

#include<cstring>  

#include<algorithm>  

using namespace std;  

  

int dp[1100][2],N,MAX;  

struct block{  

    int E[2],H;  

}B[1100];  

  

bool cmp(block a,block b){  

    return a.H>b.H;  

}  

  

int OK(int x,int S){  

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

        if(B[S].H-B[i].H>MAX)    break;  

        if(B[i].E[0]<=x&&B[i].E[1]>=x)return i;  

    }  

    return 0;  

}  

  

int main()  

{  

    int i,j,k,T;  

    scanf("%d",&T);  

    while(T--){  

        int x,y;  

        scanf("%d%d%d%d",&N,&x,&y,&MAX);      

        ///////////////////////////////////////////////木板位置初始化   

        B[0].E[0]=B[0].E[1]=x;B[0].H=y;  

        for(i=1;i<=N;i++)    scanf("%d%d%d",&B[i].E[0],&B[i].E[1],&B[i].H);  

        B[N+1].E[0]=-30000;B[N+1].E[1]=30000;B[N+1].H=0;  

        sort(B+1,B+1+N,cmp);  

        /////////////////////////////////////////////////////////  

        for(i=1;i<=N+1;i++)  dp[i][0]=dp[i][1]=1000000000;dp[0][0]=dp[0][1]=0;  

          

        int time,ans=1000000000;  

        for(i=0;i<=N;i++)  

            for(j=0;j<=1;j++){  

                k=OK(B[i].E[j],i);  

                if(k){  

                    time=dp[i][j]+B[i].H-B[k].H;  

                    if(k==N+1&&ans>time) ans=time;  

                    for(int jj=0;jj<=1;jj++)  

                        dp[k][jj]=min(dp[k][jj],time+abs(B[i].E[j]-B[k].E[jj]));  

                }  

            }  

        printf("%d\n",ans);  

    }  

    return 0;  

}  

 

补充：软件开发 , C++ ,