POJ1661Help Jimmy _dp
pooj1661将题目模型想象成水流的下落：遇到木板后分成两股水流继续向下，问什么时候能到达地面（假设地面是最后一个木板）
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++ ,
