网友投稿 487 2022-09-06
HDU 2155 小黑的镇魂曲
题目地址：#include #include #include #include #include #include #include #include #include #include const double inf = 2100000;typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;double dp[1010][2];struct node{ double left; double right; double height;} a[1010];bool cmp(node x,node y){ if(x.height != y.height) return x.height > y.height; else return x.left < y.left;}int main(){ int t; scanf("%d",&t); while(t--) { int n; double x,y,max1,m; scanf("%d%lf%lf%lf%lf",&n,&x,&y,&max1,&m); a[0].left = a[0].right = x; a[0].height = y; for(int i=1; i<=n; i++) scanf("%lf%lf%lf",&a[i].left,&a[i].right,&a[i].height); sort(a+1,a+n+1,cmp); a[n+1].left = 0; a[n+1].right = 1000; a[n+1].height = 0; for(int i=1; i<=n+1; i++) dp[i][0] = dp[i][1] = inf; dp[0][0] = 0; dp[0][1] = 0; for(int i=1; i<=n+1; i++) { for(int j=0; j max1) break; if(a[j].left >= a[i].left && a[j].left <= a[i].right) { if(i == n+1) { dp[i][0] = min(dp[i][0],dp[j][0] + a[j].height); //printf("%lf\n",dp[i][0]); dp[i][1] = min(dp[i][1],dp[j][1] + a[j].height); //printf("%lf\n",dp[i][1]); } else { dp[i][0] = min(dp[i][0],dp[j][0] + a[j].left - a[i].left + a[j].height - a[i].height); dp[i][1] = min(dp[i][1],dp[j][0] + a[i].right - a[j].left + a[j].height - a[i].height); } } } for(int j=0; j max1) break; if(a[i].right >= a[j].left && a[i].right <= a[j].right) { if(i == n+1) { dp[i][0] = min(dp[i][0],dp[j][0] + a[j].height); //printf("%lf\n",dp[i][0]); dp[i][1] = min(dp[i][1],dp[j][1] + a[j].height); //printf("%lf\n",dp[i][1]); } else { dp[i][0] = min(dp[i][0],dp[j][1] + a[j].right - a[i].left + a[j].height - a[i].height); dp[i][1] = min(dp[i][1],dp[j][1] + a[i].right - a[j].right + a[j].height - a[i].height); } } } //printf("%d %lf %lf\n",i,dp[i][0],dp[i][1]); } if(dp[n+1][0] <= m || dp[n+1][1] <= m) printf("NO\n"); else printf("YES\n"); } return 0;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~