首页 > 代码库 > POJ 1661 Help Jimmy
POJ 1661 Help Jimmy
传送门:http://poj.org/problem?id=1661
解题思路:其实吧,不难就是细节有点麻烦。
实现代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN=20005; const int INF=1<<30; struct Node{ int lx,rx,h; bool operator <(const Node &rhs) const{ return h<rhs.h; } }line[MAXN]; int dp[MAXN][2]; int main(){ int T; scanf("%d",&T); while(T--){ int N,X,Y,MAX; scanf("%d%d%d%d",&N,&X,&Y,&MAX); line[0].lx=X; line[0].rx=X; line[0].h=Y; for(int i=1;i<=N;i++) scanf("%d%d%d",&line[i].lx,&line[i].rx,&line[i].h); sort(line,line+N+1); dp[0][0]=line[0].h; dp[0][1]=line[0].h; for(int i=1;i<=N;i++){ //计算第i个板子往左的时间 int j=i-1; while(j>=0&&(line[i].lx>line[j].rx||line[i].lx<line[j].lx)) j--; if(j==-1){ if(line[i].h>MAX) dp[i][0]=INF; else dp[i][0]=line[i].h; } else{ if(line[i].h-line[j].h>MAX){ dp[i][0]=INF; } else{ int rt=INF,lt=INF; if(dp[j][0]!=INF&&line[i].h-line[j].h<=MAX) lt=dp[j][0]+line[i].lx-line[j].lx+line[i].h-line[j].h; if(dp[j][1]!=INF&&line[i].h-line[j].h<=MAX) rt=dp[j][1]+line[j].rx-line[i].lx+line[i].h-line[j].h; dp[i][0]=min(lt,rt); } } //计算往右走的时间 j=i-1; while(j>=0&&(line[i].rx>line[j].rx||line[i].rx<line[j].lx)) j--; if(j==-1){ if(line[i].h>MAX) dp[i][1]=INF; else dp[i][1]=line[i].h; } else{ if(line[i].h-line[j].h>MAX) dp[i][1]=INF; else{ int rt=INF,lt=INF; if(dp[j][0]!=INF&&line[i].h-line[j].h<=MAX) lt=dp[j][0]+line[i].rx-line[j].lx+line[i].h-line[j].h; if(dp[j][1]!=INF) rt=dp[j][1]+line[j].rx-line[i].rx+line[i].h-line[j].h; dp[i][1]=min(rt,lt); } } } printf("%d\n",min(dp[N][1],dp[N][0])); } }
POJ 1661 Help Jimmy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。