首页 > 代码库 > POJ 1661 Help Jimmy DP
POJ 1661 Help Jimmy DP
题目思路:状态转移方程很好推出,值得注意的是要分别判断是否能从一个平台的某侧移动到另一平台,也就是说要判断过一个平台的左端点或右端点做垂线,看这条垂线是否经过其他平台。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<algorithm> #define INF 0x3FFFFFFF #define MAXSIZE 1005 using namespace std; struct node { int x1,x2,h; }a[MAXSIZE]; struct node1 { int lt,rt; }dp[MAXSIZE]; int cmp(struct node A,struct node B) { return A.h > B.h; } int Check(int A,int B,int op) //OP=0 判断左侧是否联通,op=1判断右侧是否联通 { if(!op) { for(int i=A+1;i<B;i++) { if(a[A].x1>=a[i].x1 && a[A].x1<=a[i].x2) return 0; } if(a[A].x1>=a[B].x1 && a[A].x1<=a[B].x2) return 1; } else { for(int i=A+1;i<B;i++) { if(a[A].x2>=a[i].x1 && a[A].x2<=a[i].x2) return 0; } if(a[A].x2>=a[B].x1 && a[A].x2<=a[B].x2) return 1; } } int main() { int maxn,T,n,X,Y; scanf("%d",&T); while(T--) { scanf("%d%d%d%d",&n,&X,&Y,&maxn); for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h); n++; a[n].x1=-20000; a[n].x2=20000; a[n].h=0; a[0].x1=X; a[0].x2=X; a[0].h=Y; sort(a,a+(n+1),cmp); dp[0].lt=dp[0].rt=0; for(int i=1;i<=n;i++) dp[i].lt=dp[i].rt=INF; for(int i=0;i<=n;i++) { for(int j=0;j<i;j++) { if(i==n && a[j].h-a[i].h<=maxn && a[j].h-a[i].h>0) { if(a[j].x1>=a[i].x1 && a[j].x1<=a[i].x2 && Check(j,i,0)) //可从左点下落 { dp[i].lt=min(dp[i].lt,dp[j].lt+a[j].h-a[i].h); dp[i].rt=min(dp[i].rt,dp[j].lt+a[j].h-a[i].h); } if(a[j].x2>=a[i].x1 && a[j].x2<=a[i].x2 && Check(j,i,1)) //可以从右点下落 { dp[i].rt=min(dp[i].rt,dp[j].rt+a[j].h-a[i].h); dp[i].lt=min(dp[i].lt,dp[j].rt+a[j].h-a[i].h); } } else if(a[j].h-a[i].h<=maxn && a[j].h-a[i].h>0) { if(a[j].x1>=a[i].x1 && a[j].x1<=a[i].x2 && Check(j,i,0)) //可从左点下落 { dp[i].lt=min(dp[i].lt,dp[j].lt+a[j].x1-a[i].x1+a[j].h-a[i].h); dp[i].rt=min(dp[i].rt,dp[j].lt+a[i].x2-a[j].x1+a[j].h-a[i].h); } if(a[j].x2>=a[i].x1 && a[j].x2<=a[i].x2 && Check(j,i,1)) //可以从右点下落 { dp[i].rt=min(dp[i].rt,dp[j].rt+a[i].x2-a[j].x2+a[j].h-a[i].h); dp[i].lt=min(dp[i].lt,dp[j].rt+a[j].x2-a[i].x1+a[j].h-a[i].h); } } } } int ans=min(dp[n].lt,dp[n].rt); printf("%d\n",ans); } return 0; }
POJ 1661 Help Jimmy DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。