关键词：
题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=2662
1.引言：用dp解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。
但是有这样的一类题目，它们具有dp问题的特性，但状态中所包含的信息过多，如果要用数组来保存状态的话需要四维以上的数组。
于是，就要通过状态压缩来保存状态，而使用状态压缩来保存状态的dp就叫做状态压缩dp。
2.状态压缩dp的特点：状态中的某一维会比较小，一般不会超过15，多了的话状态数会急剧上升而无法压缩，一般来说需要状态压缩的也就是这一维。
3.状态压缩dp常见优化：预处理是最常见的优化，尤其是在棋盘类问题上，如果我们想进一步提高效率， 我们还可以预处理出状态之间是否可以转移而不用在每一次转移中断。
tips：注意灵活运用位运算。
下面来说这道题：
题意：有一个n*m的棋盘(n，m≤80,n*m≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻（每个棋子最多和周围4个棋子相邻）。求合法的方案总数。
思路：对于每一行，如果把没有棋子的地方记为0，有棋子的地方记为1，那么每一行的状态都可以表示成一个2进制数，进而将其转化成10进制。
那么这个问题的状态转移方程就变成了：
设dp[i] [i][k]表示当前到达第i行，一共使用了j个棋子，且当前行的状态在压缩之后的十进制数为k时的状态总数。那么我们也可以类似的写出状态转移方程：
dp[i][i][k]=sum(dp[i-1][j-num(k)][w]) num(k)表示 k状态中棋子的个数，w表示前一行的状态。
最基本的做法是：首先判断k状态是否合法，也就是判断在这一行中是否有2个旗子相邻，然后枚举上一行的状态w，判断w状态是否合法，
然后判断k状态和w状态上下之间是否有相邻的棋子。
当然这样做的时间复杂度是很高的，也就是说有很多地方可以优化，比如：判断每一行状态是否合法，可以在程序一开始判断然后保存结果，判断k状态和w状态上下之间否 有相邻的棋子，可以利用位运算，if(k&w)说明上下之间有相邻的棋子。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; #define ll long long using namespace std; ll dp[82][22][1<<9];///dp[i][j][x]第i行放了j个棋子当前状态为x时的方法数 ll mark[1<<9];///十进制标记每一行的状态 ll ans,len; ll num(ll x) ///记录状态x中1的个数 { ll sum=0; while(x) { if(x&1)sum++; x=x>>1; } return sum; } bool judge(ll x) ///判断状态x是否有相邻的棋子放在一起 { if(x&(x<<1)) return false; return true; } int main() { //freopen("in.txt","r",stdin); int n,m,k; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { memset(dp,0,sizeof(dp)); memset(mark,0,sizeof(mark)); len=0,ans=0; if(m>n) swap(n,m); for(ll i=0; i<(1<<m); i++) ///初始化第一行的放置方法数//剔除不合法状态（所谓的预处理） { if(judge(i)) ///若i状态没有相邻的棋子放在一起 { dp[1][num(i)][len]=1;///则第一行状态为len(i)时1的个数为num(i)时的方法数 mark[len++]=i;///标记状态 } } for(ll i=2; i<=n; i++) ///第二行到第n行 { for(ll j=0; j<=k; j++) ///对于放0***n个棋子 { for(ll x=0; x<len; x++) ///对于0***len-1个状态（第i行）//枚举 { for(ll y=0; y<len; y++)///对于0***len-1个状态（第i-1行）//枚举 { ll tmp=num(mark[x]);///第i行状态x中1的个数 if(((mark[x]&mark[y])==0) && j>=tmp) ///若上下2行没相邻的且当前的棋子数目大于此行当前状态所用的棋子 dp[i][j][x]+=dp[i-1][j-tmp][y];///放法数可相加 ///到当前行共用了j个棋子，当前行用了tmp个棋子，状态为x，到上一行共用了j-tmp个棋子，状态为y } } } } for(ll i=0; i<len; i++) ///枚举状态相加 ans+=dp[n][k][i]; printf("%lld ",ans); } return 0; }
poj2411状压dp经典
Mondriaan‘sDreamTimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:16771 Accepted:9683DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthed 查看详情
d.minimaxproblem(二分&状压)(代码片段)
D.MinimaxProblem(二分&状压)答案具有二分性。二分答案ansansans，将所有≥ans\\geans≥ans的数置为1，否则置为0。问题等价为是否存在两个数组或运算结果为：111111=2m−1111111=2^m-1111111=2m−1因为mmm较小，考虑... 查看详情
d.romanandnumbers(状压dp)(代码片段)
D.RomanandNumbers(状压dp)把nnn的每一位状压，问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情
uva10944nutsfornuts经典状压dp
https://vjudge.net/problem/UVA-10944//题意:给出n*m地图,起点为L,每次可以向8个方向移动,地图中有若干个果实,求搜集所有果实后再回到起点的最短路径//n,m<=20,果实个数<=15则容易用二进制记录当前拿到的果实//设dp[i][state]为当前s在果... 查看详情
codeforcesround#502d.thewu（状压预处理）(代码片段)
D.TheWutimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputChildanismakingupalegendarystoryandtryingtosellhisforgery —anecklacewithastrongsenseof"Wu" 查看详情
hdu2167方格取数状压dp（经典）(代码片段)
<题目链接>题目大意：给出一些数字组成的n*n阶矩阵，这些数字都在[10,99]内，并且这个矩阵的 3<=n<=15,从这个矩阵中随机取出一些数字，在取完某个数字后，该数字周围8个点都不能取，问：取得数字的最大和为多少... 查看详情
codeforces55d-----状压dpandmath(代码片段)
先贴一下题目链接: https://vjudge.net/problem/CodeForces-55D题意大致如下: 给t次询问， 每次询问给出一段区间【l，r】 要你求出这段区间中的beautifulnumber漂亮数定义如下: 查看详情
atcoderkeyenceprogrammingcontest2020d-swapandflip2020腾讯暑假实习笔试c(状压dpor状压乱搞)(代码片段)
...oderKeyenceProgrammingContest2020D-SwapandFlip2020腾讯暑假实习笔试(状压dpor状压乱搞)题意一张牌有正反两面，都有数字，有操作交换相邻两张卡牌，交换的时候两张牌都会翻转，问最少操作次数使得卡牌满足数字非降(n<=18)分析n<=18明... 查看详情
codeforces580d-kefaanddishes(状压dp)
...前面，那么答案再加上ci的值。输出最大值。 思路：状压dp。dp[i][j]中，i是已经选了若干个数的情况，j是最后一个被选取的数，i从选取1 查看详情
「状压dp」「暴力搜索」排列perm(代码片段)
「状压DP」「暴力搜索」排列题目描述：题目描述给一个数字串s和正整数d,统计sss有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。输入格式输入第一行是... 查看详情
bzoj1072状压dp
1072:[SCOI2007]排列permTimeLimit:10Sec MemoryLimit:128MBSubmit:2293 Solved:1448[Submit][Status][Discuss]Description 给一个数字串s和正整数d,统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中... 查看详情
fzu2188状压dp
G-SimpleStringProblemTimeLimit:2000MS MemoryLimit:32768KB 64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情
星空：差分，状压dp(代码片段)
总算不再是能用暴力卡常/随机化水过的好T3了。说是打了两个标签，实际上最关键的是题意转化。如果你丝毫不转化的话也可以：1#include<bits/stdc++.h>2usingnamespacestd;3intdp[2][1048577],b[65],k,n,m,x[9],f=1,mx;4intmain()5scanf("%d%d%d",&n,&... 查看详情
poj2411状压dp(代码片段)
#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;longlongdp[12][1<<11];boolins[1<<11];intmain()intn,m;while(scanf("%d%d",&n,&m)&&n) 查看详情
hdu5067harryanddigmachine(状压dp)（tsp问题）
题目地址：pid=5067">HDU5067经典的TSP旅行商问题模型。状压DP。先分别预处理出来每两个石子堆的距离。然后将题目转化成10个城市每一个城市至少经过一次的最短时间模型。然后简单的状压DP就可以。代码例如以下：#include<iostrea... 查看详情
状压dp找寻环的个数codeforcesbetaround#11d
http://codeforces.com/problemset/problem/11/D题目大意：给你n个点，m条边，找该图中有几个换思路：定义dp[i][j]表示i是圈的集合，j表示该集合的终点，定义起点为这些走过的点里面最小的 //看看会不会爆int!数组会不会少了一维！//取... 查看详情
bzoj4057状压dp
思路：状压一下就完了...f[i]表示选了的集合为i转移的时候判一判就好了..//BySiriusRen#include<cstdio>#include<cstring>usingnamespacestd;intcases,n,a[22][22],f[1024*1024],F;intmain(){scanf("%d",&cases);while(cases--){s 查看详情
p4163[scoi2007]排列(状压dp)(代码片段)
P4163[SCOI2007]排列(状压dp)像这种位数小的计算不同先后顺序对应的贡献的，一般就是状压dp。这里去重就用排列思想除以cnt[i]!cnt[i]!cnt[i]!时间复杂度：O(2len×n×d)O(2^len\\timesn\\timesd)O(2len×n×d)//Problem:P4163[SCOI2007]排列//Contest:Luog... 查看详情