算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述

   N个按钮在一条直线上排列,给出每个按钮的坐标(Xi,0)。每个按钮按下之后在Ti秒之后马上弹起,你一开始在最左端的按钮上,每移动1个单位长度需要1秒钟。
   请问你能否在某一时刻使所有按钮都是按下的。如果可以输出任一方案。

吐槽

   hdu 4053是同样的题目,但是spj不好用啊啊啊啊啊......

算法分析

   不仔细想是不会想到用动态规划的,因为没有重叠子问题啊...
   但是有一个比较重要的性质:如果你要按下某个区间[left,right]的按钮,那么一定是从端点开始按的...
   对于一个区间,如果你选择了先按某点k,那么你一定要经历一个left到right或者right到left的过程。
   在这个过程中,完全有按下k的机会。所以先按k就浪费了...
   K的确可能是最优的,但是先按端点一定不会比K差 这样的话就可以DP了。
   于是状态就可以表示成dp[left][right][p],p=0和p=1分别表示从左端或者从右端进入区间[left,right]花费的最小时间。
   决策分两种 : 按下左端点,那么就从左端进入区间[left+1,right]。并判断T[l]是否大于dp[left+1,right,0]+cost[l,l+1]。 按下右端点同理。
   然后记录一下这个区间的最优决策。DP完之后就可以递归的输出决策了,输出时有个trick: 行尾不要有额外的空格。
   解决办法也很简单:区间[i,i]一定是最后进入的,也就是最后输出的决策。
   代码参照shi哥的吧...
posted on 2012-04-25 12:01 西月弦 阅读(878) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理