基于状态压缩的动态规划.pdf

青少年信息学奥林匹克竞赛 1 基于状态压缩的动态规划 By tqzx 2015年4月 动态规划作为一种常见的算法，已在信息学竞赛中屡见不鲜；而各种状态的表示作为规 划的核心内容也畅快为各位选手所熟知。但现在经常有这么一种题，它利用我们常见的各种 状态表示就会具有后效性，而用搜索又无法满足时间的要求。这时就需要我们对状态的表示 进行改进。基于状态压缩的动态规划这时候就会显示出它的效能来。 普通的动态规划一般是以一个个元素作为状态，或者是以一整块作为状态，这样虽然直 观清楚，但记录地信息太少，就可能导致后效性的存在。而状态压缩模型则是把许多个元素 的状态（比如一行）作为一个整体来表示状态，这样就为下面的计算提供了更多的信息，从 而保证了正确性。但是由于是多个元素的集合体，所以要在计算机上存储就要把它压缩，具 体的方法见后面的例题。 一、预备知识 1 1 11、位操作 位操作是一种速度非常快的基本上，有左移、右移、与、或、非等运算。 1）左移运算shl（C++中为 ）：左移一位，相当于某数乘以2。如：二进制数110左 移1 位，变为1100（二进制形式），由6变为12，运算可表示为：6shl1（C++: 61），结 果为12。因此，左移x位，相当于该数乘以2^x； 2）右移运算shr（C++中为 ）：右移一位，相当 于某数除以2，比如二进制110右 移1位，变为 11（二进制形式），即由6 变成3，运算可表示为：6 shr1（C++: 61），结 果为3。因此，左移x位，相当于该数除以2^x。 3）与运算and（C++中为：）：按位进行“与”运算，运算的两个数相应位均为1 时 则结果该位为1，否则结果该位为0。如：5 and 6 （C++: 56)，结果为4（相应二进制运 算形式：101与100 按位与，结果为二进制100 即十进制的4）。 4）或运算or（C++中为：|）：按位进行“或“运算，运算的两个数相应位均为0 时， 结果该位为0，否则该位为1。如：5or 6 （C++中5|6）=7。 5）非运算not（C++中为：~）：按位取反。 2 2 22、位操作的应用 若当前状态为s，则s有下列操作应用（以下以C++中的算符举例）： 1）判断一个数的二进制形式的第i位是否为0： s1i)=0，意思是将1左移i位与s 进行与运算后，看结果是否为0。 2）将一个数的二进制形式的第i位置为1： s|1i，意思是将1 左移i 位与s进行或运 算。 3）将一个数的二进制形式的第i位置为0: s~(1i)，意思是s与第i 位为0，其余各 @程老师电脑培训 青少年信息学奥林匹克竞赛 2 位为1 的数进行与运算。 例：s=(1010101)2，i=5 s1i：2 (0100000)2=0 s|1i：（1010101）2| (0100000)2=(1110101)2 s~(1i)：（1010101）2 （1011111）2=（1010101）2 二、例题 骑士 【问题描述】 在n*n（1≤n≤9）的棋盘上放k（0≤k≤n*n）个国王，使他们互不攻击（注：国王可 攻击其相邻的8 个格子上的棋子），求放置国王的方案总数。 【输入】 输入有多组方案，每组数据只有一行，为两个整数n 和k。 【输出】 每组数所对应一行输出，为放置国王的方案总数（若不能够放置，则输出为0）。 【输入样例】horse.in 3 2 4 4 【输出样例】horse.out 16 152 【问题分析】 由问题很容易联想起经典的“八皇后”问题，似乎就是“皇后”变成了“国王”，而且 格子数范围似乎也差不多，所求问题也一样。那么这个问题也能用搜索解决吗？ 可稍加分析可知，搜索是很难胜任的。因为国王的数目可以很大，加上它与“八皇后” 问题的一个本