dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Hdu 3237 Help Bubu

题目描述:

    原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=3237

    题目可以抽象成这样,有0~7这样8个数字组成的数字串,可以抽出k个数字再插回到任意位置,问最后不同的数字段(相同的数字组成一段,例如00077112有4段,000为一段,77为一段……)

 

题目分析:

    这个题乍一看很像动态规划,但是真的是动态规划,不过我还是第一次做这样的动态规划。

    参考了一位大牛的报告,地址如下:

F[i][j][k][s],表示前i本书,拿走j本,留下的书最后一本高k(呃我觉得这个很巧妙),留下的书的组合为s(例如1010000表示高度为0的,高度为2的书有留下的)

    状态转移部分伪代码(当处理到f[i][j][k][s]时)

(1)  考虑第i本书不抽走,在f[i-1][j][k][s]存在的前提下(也就是处理到i-1本书的时候,这个状态下,留下的最后一本书高度为k):

若这本书的高度也是k,那么这本书的加入不会造成混乱度的提升,f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s])

若这本书的高度不是k,那么这本书的加入会造成混乱度增加1,则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s] + 1)

(2)考虑抽走第i本书,f[now][j+1][k][s] = min( f[pre][j][k][s], f[now][j+1][k][s])

最后处理答案的时候要考虑一下那些被抽走的书还是要插回去的。如果有一本高度为h的书被抽走,剩下的书里头都没有高度为h的,那么混乱度需要增加。

 

代码:

hdu3237
posted on 2010-08-26 20:44 Dango 阅读(473) 评论(0)  编辑 收藏 引用

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