我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划 >

动态规划经典模型之状态压缩模型及树状

归档日期:06-10       文本归类:动态规划      文章编辑:爱尚语录

  定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!NOIP2018冬令营火热报名中!

  动态规划基本会出现在信息学比赛的各类考试中,理解动态规划,学会动态规划的思想对于信息学的同学们来说至关重要!

  有一些动态规划的状态并不是放与不放,取与不取,选与不选那么简单。状态可能因为情况而变得很多,比如在一个n*m(n=500,m=10)的棋盘里面放棋子,有些格子被挖掉不能放棋子,并且任何两个棋子不得有上下左右的相邻,问最多放多少个棋,该怎么做呢?

  先分析是否有后效性,发现任何一行在其下一行没有被放置的时候,都只受上一行的影响,于是满足了无后效性。

  具体的做法是,把每一行的摆放情况看成一个二进制数,放了的地方是1,不放的地方是0,因此,每一种状态都可以用唯一一个数字来表示,于是就可以记录当前状态最多可以放多少个棋子了。

  这里有一个优化,有些状态本身就是不合法的,如23(10111)在同行中就不满足,应该完全不考虑。所以,先进行预处理把所有可能的状态求出来是很必要的。

  第一行的每一个状态的棋子数等于本身这个状态所拥有的棋子数。在状态转移中,第k行的第s个状态可以为k-1行所有可能的状态数的和加上本身状态所拥有的棋子数,至于两状态是否冲突,可以使用位运算判断。

  本算法的时间复杂度为O(n*(2^m)^2),当m比较小时,此算法还是很快了。

  由于状态压缩中使用的空间比较大,通常是指数级别的,所以推荐使用滚动数组来记录。

  有一些状态压缩模型并不是描述前一行的状态就可以了这么简单,如NOI2001的炮兵阵地一题:

  司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示)。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队)。

  一支炮兵部队能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。炮兵的攻击范围不受地形的影响。

  现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。

  接下来的N行,每一行含有连续的M个字符(‘P’或者‘H’),中间没有空格。按顺序表示地图中每一行的数据。N≤100;M≤10。

  不过对于这个题可没有那么简单,每一行的状态跟前两行有关,并且两行相互有干扰。说不简单也简单,于是考虑多记录些东西。用a[1..2^m,1..2^m]来记录两行共同的状态就可以了。至于初始情况和状态转移类似于上一题,所以不写了。本题同样需要先算出状态和使用滚动数组,最后再选取一个最大值即可。

本文链接:http://quangdungfc.net/dongtaiguihua/307.html