首页 > 笔记 > 状态压缩总结

状态压缩总结

状态压缩是DP的一中神奇的方法。涉及到了非常有趣的二进制思想。

引言

在生活中我们经常接触一些和善的P问题,他们有O(1),O(log(n)),O(n^a)等多项式级的复杂度的问题,因为它的规模n出现在底数的位置;

当然还有一些恐怖的NPC问题,他们就是噩梦,因为他们的算法没有多项式级的解法,只有O(a^n)和O(n!)型复杂度,它是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

但是有没有好的解决方法呢,当然有,那就是——状态压缩

现在要普及一些基础知识(当然你也可以看 位运算技巧

images

(来自网络

更实用的技巧

如果要获得第i位的数据,判断((data&(1<<i-1))==0),若真,为0,假,为1; (把1移到i-1的位置,用&判断一下)
如果要设置第i位为1,data=(data|(1<<i-1));    (把1移到i-1的位置,加上data)
如果要设置第i位为0,data=(data&(~(1<<i-1)));     (把1移到i-1的位置,取反,&一下)
如果要将第i位取反,data=(data^(1<<i-1));   (把1移到i-1的位置,异或一下)
如果要取出一个数的最后一个1(lowbit):(data&(-data))         (这里利用的是负数取反加1实际上改变的是二进制最低位的1这个性质)

注意:

位运算的运算优先级非常低,位运算时一定要加括号

在写状压的时候,有一个很好用的工具

images

就是它

程序员模式

Lsh 是左移 Rsh 是右移 RoL 是右移1 RoR 是左移1

正文

例1

第一个例子并不是状态压缩

它是一个搜索

拯救公主

images

样例输入

样例输出

传送门

这题是loli让我们刷搜索的时候意外找到的题。

求最短当然是广搜。广搜需要记录走过的位置以防重复(假如不想T死),可是不止记录坐标,也要记录收集了多少宝石。于是我们在广搜里加入一个状态表示每个宝石是否已经收集到了,如果收集到了新的宝石,那么先前不能vis的就可以重复走了。

问题在于怎么表示宝石的状态?观察数据范围,最多4个宝石。

压缩成二进制,可以有效解决。用这一位是1表示这个宝石收集过,用0表示这位宝石没有拿到,走到终点时判断有几个1即可。

 

这是一道很好的入门题,值得一做

一定要注意细节

代码

选做题

符号三角形

images

样例输入

样例输出

 

传送门

这题是一道打表题= = 但是通过非常蛋疼的状压优化完全可以不代表做出来

具体见注释

例2

poj 3254 Corn Fields

题目描述

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

农场主John新买了一块长方形的新牧场,这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12),每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。

遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是John不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。

John想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)

输入输出格式

输入格式:
第一行:两个整数M和N,用空格隔开。

第2到第M+1行:每行包含N个用空格隔开的整数,描述了每块土地的状态。第i+1行描述了第i行的土地,所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块土地不适合种草。

输出格式:
一个整数,即牧场分配总方案数除以100,000,000的余数。

输入输出样例

输入样例#1:
2 3
1 1 1
0 1 0
输出样例#1:
9

(翻译来自luogu

 

这是一道很好的状压入门题。

开始前我们先预处理一下各种情况

我们先不管草地的情况和列的情况,单看行中的情况

每一行都是一样的!

都是隔一格放一个

那么我们就可以预处理一下每一行的情况。

那么如何转移呢

假如读入的时候我们用1表示不能放牧

那么假如现在的草地的情况为

草地:00010001

放牛:11001110

那么我们把这两个数&一下就成了

结果:00000000

也就是说,假如放牛与草地不冲突,那么它们&的结果就是0

这样就可以判断冲突了

假如要两列不冲突,其实是一样的,只要&一下就行了

这样就得出了方程

i表示当前行,j表示当前行的情况,k表示上一行的情况

最后

注意细节

代码

poj 1185 炮兵阵地

Description

司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用”H” 表示),也可能是平原(用”P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示:

images
如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input

第一行包含两个由空格分割开的正整数,分别表示N和M;
接下来的N行,每一行含有连续的M个字符(‘P’或者’H’),中间没有空格。按顺序表示地图中每一行的数据。N <= 100;M <= 10。
Output

仅一行,包含一个整数K,表示最多能摆放的炮兵部队的数量。
Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output

6

这道题和上一道题思路基本一样,可以检测一下

 

核心代码

nu中存的是这一行中能放炮的数量

代码

例4

poj 2411 Mondriaan’s Dream

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

images
Expert as he was in this material, he saw at a glance that he’ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won’t turn into a nightmare!

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

images

Sample Input

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

Sample Output

1
0
1
2
3
5
144
51205

题意就是用12和21的小块覆盖矩阵

这是一种不相同的状压

具体见这里

 

To be continued…

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×