http://acm.hdu.edu.cn/showproblem.php?pid=2155经典的DP，很多地方都见到过有类似的题目，一直想A
就像是“是男人就下100层”这个游戏一样
今天终于A掉了，爽~！
其实这个状态转移方程很早的时候就想到了，觉得也不是很难阿，不知道为什么这么少人过。。。
dp[i][0]和dp[i][1]分别记录起点到台阶i左端右端的最短距离
然后j=i-1
一直找到高度差小于max的台阶j并判断能不能下降到台阶i
首先处理起点下降到达第一个台阶。
接着就可以写状态转移方程了
hh是记录台阶的数组
这个是j的左端到达台阶i的方程
右端的把0改成1也相仿
dp[i][0] = Min(dp[i][0],dp[j][0] + hh[j].high - hh[i].high + hh[j].left - hh[i].left);
dp[i][1] = Min(dp[i][1],dp[j][0] + hh[j].high - hh[i].high + hh[i].right - hh[j].left);
最后自己定义
hh[n].high = 0;
hh[n].left = -1;
hh[n].right = 1001;
来表示地面，找到一个最小值和deadline比较。。。YES还是NO就ok了。。。
但是其实一句话让我找错找了好久
“当小黑又处于平台边缘的时候，他开始继续下落”
我以为刚刚好掉在平台边缘的时候继续下落不算是在平台上
判断能不能到达平台的语句：
if(hh[end].left<key && key<hh[end].right)
改成
if(hh[end].left<=key && key<=hh[end].right)
才AC。。。。
posted on 2009-02-20 16:00
shǎ崽 阅读(468)
评论(0) 编辑 收藏 引用