hdu2155 小黑的镇魂曲(dp)
题意:
小黑的镇魂曲
Problem Description
这个事情发生在某一天,当小黑和SSJ正在约会的时候,邪恶的Guner抓走了SSJ,小黑伤心万分,怒不可遏啊!但是他显然也是没有办法的,谁叫Guner比小黑邪恶,小黑打不过Guner呢!于是,小黑利用皮肤保护色,趁夜摸黑前往Guner的城堡,准备偷偷摸摸的把SSJ拯救出来,但是只要小黑一打开SSJ身上的锁链,看门的葱头就会在M秒以内通知Guner,Guner马上超时空转移,闪到小黑身边抓住他们,于是小黑虽然跑得不快,但是他也不得不跑啊。由于Guner的城堡构造特殊,它是由一个一个的平台搭建成的,所以小黑的逃跑路线是这样
的,在时刻0的时候,他位于最高点,也就是高于所有的平台,然后他开始垂直下落,他的下落速度是1米/秒。当小黑下落到某个平台上时,他可以向左跑也可以向右跑,他的跑动速度还是1米/秒。当小黑又处于平台边缘的时候,他开始继续下落。但是小黑是个怜香惜玉的人,为了顾及怀中的SSJ,于是他每次下落的最大高度不会超过MAX米,不然SSJ摔坏了,Guner也懒得追了,小黑也会伤心致死的。但是只要小黑抱着SSJ一落到地面,Guner就再也抓不住他们了。
Input
第一行输入一个数T(0 < T <= 10),表示测试数据的组数。每组测试数据的第一行是5个整数,N,X,Y,MAX,M,用空格分开。N(0 < N <= 1000)是台阶的数目,X,Y分别是小黑0时刻所在位置的横、纵坐标,MAX表示小黑最多能下落的高度,M表示从小黑一打开锁链葱头发觉后报告给Guner的时间,接下来有N行数据,每行数据描述一个台阶,包括3个数据,Xl[i],Xr[i],H[i],其中Xl[i](0 < Xl[i] <= 1000)表示当前台阶最左边的边的X坐标,Xr[i](0 < Xr[i]
<= 1000)表示当前台阶最右边的边的X坐标,H[i](0 < H[i] < 1000)表示当前台阶
离地面的高度。数据确保小黑和SSJ是能到达地面的。
Output
每组测试数据当Guner能抓住小黑和SSJ时,输出YES,否则输出NO.
Sample Input
1
1 10 17 20 20
1 8 7
Sample Output
NO
思路:
哎!这个题目敲了60多遍,有点伤心了,当时想的是用最短路,因为是1000*1000的坐标,最多也就是1000*1000那么多的点,然后是边,边也没有多少,估计大约600多万,建边的话,对于每一个下降,我都建3条边,当前点到下落点,下落点到下落边的左端点,下落点到下落边的右端点(注意一个点下落最多降落在一条边上,因为无法传过边),把能下落的点都mark上,最后在吧所有没mark并且能到达地面的和地面连接一条边,跑起点到地面的最短路,结果wa了好多次,后来wa的我自己都蒙了,以为是什么重边啊什么的(蒙圈了),最后用的dp过的,哎!真心不明白自己的最短路那个地方错了,这个题目要是用dp还是很同一弄的,和刚接触dp时的那个数塔差不多,对于每一条边,我们用他的做端点(和右端点)更新下面的可达边的左右端点的最优值,dp[i][0]表示的是第i条边的做端点的最优,dp[i][1]表示的是i条边右端点的最优,然后就往下更新就行了,记住一点就是一个点下落对多只能降落到一条边上,所以先sort下,然后第一次降落之后就break,具体看代码吧。
#include<stdio.h>
#include<string.h>
#include<algorithm> #define N 1100
#define INF 1000000000
using namespace std; typedef struct
{
int l ,r ,h;
}NODE; NODE node[N];
int dp[N][2]; bool camp(NODE a ,NODE b)
{
return a.h > b.h;
} int minn(int x ,int y)
{
return x < y ? x : y;
} bool solve(int n ,int maxx ,int t)
{
for(int i = 1 ;i <= n ;i ++)
dp[i][0] = dp[i][1] = INF;
dp[1][0] = dp[1][1] = 0;
sort(node + 1 ,node + n + 1 ,camp);
for(int i = 1 ;i <= n ;i ++)
{
for(int j = i + 1 ;j <= n ;j ++)
{
if(node[i].h - node[j].h > maxx) break;
if(node[i].l >= node[j].l && node[i].l <= node[j].r)
{
if(j == n)
{
dp[j][0] = minn(dp[j][0] ,dp[i][0] + node[i].h);
dp[j][1] = minn(dp[j][1] ,dp[i][0] + node[i].h);
}
else
{
dp[j][0] = minn(dp[j][0] ,dp[i][0] + (node[i].h - node[j].h) + (node[i].l - node[j].l));
dp[j][1] = minn(dp[j][1] ,dp[i][0] + (node[i].h - node[j].h) + (node[j].r - node[i].l));
}
break;
}
} for(int j = i + 1 ;j <= n ;j ++)
{
if(node[i].h - node[j].h > maxx) break;
if(node[i].r >= node[j].l && node[i].r <= node[j].r)
{
if(j == n)
{
dp[j][0] = minn(dp[j][0] ,dp[i][1] + node[i].h);
dp[j][1] = minn(dp[j][1] ,dp[i][1] + node[i].h);
}
else
{
dp[j][0] = minn(dp[j][0] ,dp[i][1] + (node[i].h - node[j].h) + (node[i].r - node[j].l));
dp[j][1] = minn(dp[j][1] ,dp[i][1] + (node[i].h - node[j].h) + (node[j].r - node[i].r));
}
break;
}
}
}
return dp[n][0] <= t || dp[n][1] <= t;
} int main ()
{
int n ,x ,y ,max ,t ,T ,i;
scanf("%d" ,&T);
while(T--)
{
scanf("%d %d %d %d %d" ,&n ,&x ,&y ,&max ,&t);
node[1].l = node[1].r = x ,node[1].h = y;
for(i = 1 ;i <= n ;i ++)
scanf("%d %d %d" ,&node[i+1].l ,&node[i+1].r ,&node[i+1].h);
n += 2;
node[n].l = 0 ,node[n].r = 1001 ,node[n].h = 0;
if(solve(n ,max ,t)) printf("NO\n");
else printf("YES\n");
}
return 0;
}
最新文章
- iOS在导航栏上居中显示分段控件(UISegmentedControl)
- Js删除数组重复元素的多种方法
- JS 将字符串转换成日期类型
- [转]ACM进阶计划
- org.apache.ibatis.builder.IncompleteElementException: Could not find parameter map
- Android ActivityThread(主线程或UI线程)简介
- extern &ldquo;C&rdquo;原理,用法以及使用场景-2016.01.05
- Linux下core文件产生的一些注意问题
- vb6加载时提示出错,窗体log文件中错误信息为:控件 XX 的类 MSComctlLib.ListView 不是一个已加载的控件类。
- Java对象的创建
- pat1101-1110
- session.save()返回值问题
- MTK 软件设置路径
- k8s 网络模型
- 获取Vue的实例方法
- 【持续更新】 | OpenCV 学习笔记
- 【PAT】B1061 判断题(15 分)
- C和C指针小记(九)-指针用法1
- JAVA将异常的堆栈信息转成String
- npm 切换淘宝源