下载文档原格式
状态压缩动态规划状压DP总述状态压缩动态规划，就是我们俗称的状压DP，是利⽤计算机⼆进制的性质来描述状态的⼀种DP⽅式很多棋盘问题都运⽤到了状压，同时，状压也很经常和ＢＦＳ及ＤＰ连⽤，例题⾥会给出介绍有了状态，DP就⽐较容易了举个例⼦：有⼀个⼤⼩为n*n的农⽥，我们可以在任意处种⽥，现在来描述⼀下某⼀⾏的某种状态：设n = 9；有⼆进制数 100011011（九位），每⼀位表⽰该农⽥是否被占⽤，1表⽰⽤了，0表⽰没⽤，这样⼀种状态就被我们表⽰出来了：见下表列数123456789⼆进制100011011是否⽤√×××√√×√√所以我们最多只需要 2n+1−1 的⼗进制数就好（左边那个数的⼆进制形式是n个1）现在我们有了表⽰状态的⽅法，但⼼⾥也会有些不安:上⾯⽤⼗进制表⽰⼆进制的数，枚举了全部的状态，DP起来复杂度岂不是很⼤？没错，状压其实是⼀种很暴⼒的算法，因为他需要遍历每个状态，所以将会出现2^n的情况数量，不过这并不代表这种⽅法不适⽤：⼀些题⽬可以依照题意，排除不合法的⽅案，使⼀⾏的总⽅案数⼤⼤减少从⽽减少枚举位运算有了状态，我们就需要对状态进⾏操作或访问可是问题来了：我们没法对⼀个⼗进制下的信息访问其内部存储的⼆进制信息，怎么办呢？别忘了，操作系统是⼆进制的，编译器中同样存在⼀种运算符：位运算能帮你解决这个问题（基础，这⾥不打算⾃⼰写了，参照，以下内容也复制⾃qxAi的这篇博客，这⾥谢谢博主）为了更好的理解状压dp，⾸先介绍位运算相关的知识。
1.’&’符号，x&y，会将两个⼗进制数在⼆进制下进⾏与运算，然后返回其⼗进制下的值。
例如3(11)&2(10)=2(10)。
2.’|’符号，x|y，会将两个⼗进制数在⼆进制下进⾏或运算，然后返回其⼗进制下的值。
例如3(11)|2(10)=3(11)。
3.’’符号，x y，会将两个⼗进制数在⼆进制下进⾏异或运算，然后返回其⼗进制下的值。
DP问题不完全总结1.按状态类型分写在前面：从状态类型分，并不表示一题只从属于一类。
其实一类只是一种状态的表示方法。
可以好几种方法组合成一个状态，来解决问题。
1.1.编号(长度)动态规划共性总结本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。
一般来说，有两种编号的状态：状态(i)表示前i个元素决策组成的一个状态。
状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。
题库a)最长不下降子序列以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。
于是很容易想到O(n2)得算法。
但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到O(nlogn)。
关于优化详见优化章。
一些问题可将数据有序化，转化成本题。
应用：拦截导弹(NOIP99 Advance 1)就是原题。
Beautiful People(sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排列，另一个权作为第二关键字不上升。
Segment(ural 1078)，将线段的左端点有序化就可以了。
b)LCS状态(i,j)，表示第1个字符串的第i位，与第2个字符串的第j位匹配，得到的最长的串。
若有多个串要LCS，则加维，即几个串就几个维。
我也将此题归入路径问题。
c)花店橱窗布置(IOI99)见路径问题。
1.2.区间动态规划共性总结本类问题与下一章的划分问题的决策的分割点无序交集比较大(占本类问题的30%)。
题库a)石子合并见划分问题b)模版匹配(CEOI01,Patten)这题特殊的地方是状态的值是一个集合而不是一个数。
c)不可分解的编码(ACM World Final 2002)d)Electric Path(ural1143)e)邮局(IOI2000 Day2 1)若状态表示的思路从第i个村庄可以从属于哪个邮局，无最优子结构。
转变一个方向：第k个邮局可以"控制"一个区间的村庄[i,j]。
一道状态压缩DP的详细思路难易指数：★★★河北省衡水中学高亚在动态规划的过程中，状态的表示有时候很是恶心，不容易表示出来，所以，我们需要用一些编码技术，将这些状态表示出来，最常用的方法是用一个二进制数来表示一个集合的状态，下面通过一道例题来对状态压缩DP进行分析一、题目问题描述小keke同学非常喜欢玩俄罗斯方块（**）,他最近发现传统的俄罗斯方块很无趣，于是他想到了一个新规则的游戏来考验你。
游戏是这样的：给定你一个宽度为w的游戏场地，我们设高度为正无穷。
现在给你3种俄罗斯方块：1*2的方块2*2的方块2*2的方块去掉一个1*1的方块如果你明白俄罗斯方块的规则的话，方块在下落过程中是可以随便旋转的。
而且是从上往下落，上面的落在下面的上面。
现在给定你一个高度h，让你求出有多少种游戏的方法，使得最后恰好落满h的高度（最上层是齐平的）。
因为这样可以得很多很多分。
输入数据两个整数h,w含义如题所述输出数据一个整数，为能达到要求的游戏方法的总数。
样例输入2 2样例输出3数据范围1<=h,w<=9,注意答案有可能很大（你懂得，用不到高精度）二、关于状态压缩的思路首先，先根据题意，将这个俄罗斯方块的所有形状都画出来（注意这些方块已经标上号了，下面直接引用不加说明）观察到只有七种情况，并且它们的高度只有两行，所以，一个俄罗斯方块最多只会影响上一行或下一行，而不会影响其他行题目中给出的高度，宽度最多只有9，用二进制位完全可以满足要求，所以可以用0表示这个地方是空的，1表示这个地方已经被填充了木块，那么可以很方便的用两个十进制数来表示两行的状态设f[i][j]表示前i行，并且第i行状态为j的最多方案数，那么因为第i行的放置方案仅仅只会影响上一行，所以可以得以下方程：f[i][j]=∑f[i−1][j′]其中，要求第i-1行的j'状态能够推到j这个状态来个最简单的例子，一个2*2的方格，从空的状态到把它填满，方案数是多少？（其实就是样例）可以看到，如果用刚才的方法，直接用0表示不填，用1表示填，那么这三种方案的状态表示是一样的，所以如果只是简单的求和，方案数就只是简单的1，并不是我们想要的结果，如何满足这一点的要求呢？其实可以采用预处理的方法，预处理出从状态i到状态j的方案数有多少种，记录到g[i][j]数组中（如果不能转移到，那么g[i][j] = 0），然后在方程转移的时候，直接采用下面的方程：f[i][j]=∑g[j′][j]∗f[i−1][j′]其中j'还是老规矩，能从j'状态推到j这个状态因为有了g[j'][j]这个从j'状态推到j状态的方案数，所以在i-1行状态为j'时，想推到第i行状态为j，共有g[j'][j]种方案可以选择，根据乘法原理，所以f[i-1][j']的方案数乘以g[j'][j]就可以得到f[i][j]，最后针对每种状态，求和即可好了，我主要想说的是如何进行预处理，最后还想说说方程中f数组的初值问题。
状压dp（总结）状态压缩状压这个和二进制分不开关系所以，对于二进制的熟悉是必不可少的技能& 与操作，1不变，0变0| 或操作，0不变，1变1^ 异或操作,0不变，1取反～取反操作，把每一个二进制位0变1，1变0还有一些复杂操作可以根据这些去理解状态压缩所谓状态压缩就是把dp的每一次转移时的状态用二进制来表示或者用二进制来间接表示比如这里有10个苹果，编号1-10我拿走了1,4,7,9这四个苹果那么我们可以用011011010这一串二进制数来表示现在的状态0表示这个位置没有苹果，1表示有那么这就是一个状态相比拿一个bool型的数组，这样表示更方便，内存更小，操作更简单现在我想把拿走的苹果放回去，没拿走的拿走那么状态就变成100100101直接取反 a=011011010 b=100100101a==～b;这时候就充分展示了状态压缩的快捷性下面我们讲一道例题。
在n*n(n≤20)的方格中放置n个车，每个车可以攻击所在的行和列，求方案总数直接上排列组合，n！，很好理解啊在n*n(n≤20)的方格棋盘上放置n 个车，某些格子不能放，求使它们不能互相攻击的方案总数。
这时候一些格子不能放，就要考虑每一行的情况但是，，，，即使每一行中有的格子不能放，最终还是每一行每一列都要有一个车子所以我们用s这个int型的数来表示现在的状态（行状态）如果这一列现在有车子，那这一位就是1所以最终s一定会变成11111111111（全是1）只有这样才能把n个车全部放进去这样这一状态有几个车子说明这就是第几行那这样转移方程就有了dp[s]+=dp[s^(s&-s)];for(;j>0;j-=(j&-j)){dp[i]+=dp[i^(j&(-j))];}还有个问题，有些格子不能放车这怎么办还记得前面的苹果吗用1表示这里能放车子，0表示不可以在状态转移的时候&一下就可以啦j=i&s[num];代码如下#include<bits/stdc++.h>#define ll long longusing namespace std;int n,m;long long dp[1<<20];int s[25];int main(){memset(s,0x7fffffff,sizeof(s));//if(s[1][1]==1)cout<<"sh";//cout<<(s[1][1]&0)<<endl; scanf("%d%d",&n,&m);int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);s[x]-=(1<<(y-1));}dp[0]=1;for(int i=1;i<(1<<n);i++){int j,num=0;for(j=i;j>0;j-=(j&(-j))){num++;}j=i&s[num];for(;j>0;j-=(j&-j)){dp[i]+=dp[i^(j&(-j))];}}printf("%lld",dp[(1<<n)-1]);}这样基本的状压dp就结束了也许你已经发现了所有的n都小于等于20因为int只有32位这也是状压的前提所以当你一直为空间时间复杂度着急时就去考虑状压而状压前先找到可以状压的数就是32位以内的over。
周赛350（模拟、脑经急转弯、状压DP、动态规划）难度简单4卡车有两个油箱。
给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。
该卡车每耗费 1 升燃料都可以行驶 10 km。
每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。
返回卡车可以行驶的最大距离。
提示:从辅助油箱到主油箱的燃油喷射是不连续的。
每消耗5升燃油，此事件就会突然发生。
示例 1：输入：mainTank = 5, additionalTank = 10输出：60解释：在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。
使用完剩余的1升燃油后，没有新的燃油注入主油箱，主油箱变空。
总行驶距离为 60km 。
示例 2：输入：mainTank = 1, additionalTank = 2输出：10解释：在用完1升燃料后，主燃料箱变空了。
总行驶距离为 10km 。
提示：•1 <= mainTank, additionalTank <= 100模拟classSolution{publicintdistanceTraveled(int mainTank,int additionalTank){int ans=0;while(mainTank >=5){ans +=50;mainTank -=5;if(additionalTank >0){additionalTank -=1;mainTank +=1;}}ans += mainTank *10;return ans;}}数学classSolution{publicintdistanceTraveled(int mainTank,int additionalTank){return(mainTank+Math.min(additionalTank,(mainTank-1)/4))*10;}}难度中等1给你一个正整数数组 nums 。
状态压缩dp炮兵阵地Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 8971 Accepted: 3169Description司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。
一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input第一行包含两个由空格分割开的正整数，分别表示N和M；接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。
按顺序表示地图中每一行的数据。
N <= 100；M <= 10。
Output仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
Sample Input5 4PHPPPPHHPPPPPHPPPHHPSample Output6SourceNoi 01这道题是一道典型的状态压缩DP。
注意到每一行炮兵的摆放只和前两行有关系，便可以记录一个f数组，f[h,i,j]表示第h行的状态为st[i]，第h-1行的状态为st[j]。
现在的关键就是如何快速求f[h,i,j]。
注意到求f数组跟状态数有关，那么便优化状态。
首先是状态的存储。
注意到m范围较小，便可以按行存储。
对于每一行，如果一个格子放了炮兵，就看成1，否则看成0，然后记下对应数列的十进制值即可。
但这样共有2^m种状态，显然太多了。
注意到有很多状态其实是不可能的(即某个炮兵附近还有炮兵)，我们就可以再预处理状态时加一些判断。
那么如何高效判断呢？对了，可以用位运算！判断过程如下：for i:=0 to 1 shl m-1 dobeginif i and (i shl 1)<>0 then continue;//错一位进行判断if i and (i shl 2)<>0 then continue;//错两位进行判断inc(sl);st[sl]:=i;count[sl]:=calc(i);//count数组记录每个序列中1的个数end;解决了存储问题后，整个程序就很简单了，剩下的DP不再赘述，详见程序。
贴代码：/code/view/18264/var f:array[1..100,1..70,1..70] of integer;map:array[1..100] of integer;st,count:array[1..70] of integer;n,m,sl:integer;function calc(x:integer):integer;var sum:integer;beginsum:=0;while x<>0dobeginsum:=sum+x mod2;x:=x shr1;end;exit(sum);end;procedure init;var i,j:integer;ch:char;beginreadln(n,m);sl:=0;for i:=0to1shl m-1dobeginif i and (i shl1)<>0then continue;if i and (i shl2)<>0then continue;inc(sl);st[sl]:=i;count[sl]:=calc(i);end;for i:=1to n dobeginmap[i]:=0;for j:=1to m dobeginread(ch);if ch='H'then map[i]:=map[i]+1shl (m-j);end;readln;end;end;function max(a,b:integer):integer;beginif a>b then exit(a) else exit(b);end;procedure work;var h,i,j,k:integer;beginfor i:=1to n dofor j:=1to sl dofor k:=1to sl dof[i,j,k]:=-1;for i:=1to sl doif map[1] and st[i]=0then f[1,i,1]:=count[i];for h:=2to n dofor i:=1to sl doif st[i] and map[h]=0thenfor j:=1to sl doif st[j] and st[i]=0thenfor k:=1to sl doif (st[k] and st[i]=0) and (st[k] and st[j]=0) thenif f[h-1,j,k]<>-1thenf[h,i,j]:=max(f[h,i,j],f[h-1,j,k]+count[i]); end;procedure print;var i,j,ans:integer;beginans:=0;for i:=1to sl dofor j:=1to sl doans:=max(ans,f[n,i,j]);writeln(ans);end;begininit;work;print;end.poj1038(状态压缩dp)DescriptionBugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.TaskY ou are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Y our task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.InputThe first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x andy (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).OutputFor each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.Sample Input26 6 51 44 62 23 66 46 5 43 36 16 26 4Sample Output34SourceCEOI 20022008-08-30 20:40题意如下:Bug Integrated公司正准备生产6TB的Q-RAM芯片，每块芯片都是由2*3的小芯片组成的。
