关键词：
状压DP入门及理解
*（另类的暴力）*
一般状态数不多的时候就会开数组，但是有的状态并不好表示，于是，状压DP就产生了。
状压DP应该是分两类的，一类是压缩状态，另一类是舍弃状态。 我感觉初学状压DP难就难在二进制运算的应用，了解二进制运算符就显得十分重要。
所以我们先看下表，如果有不会二进制简单应用的请点击https://blog.csdn.net/sinat_35121480/article/details/53510793（神犇请忽略...）
下面就可以看题了：
对于状压压缩，入门题[USACO06NOV]玉米田和Corn Fields[SCOI2005]互不侵犯，思路基本上相同。
我自己做了这两个题有两点体会，如下：
第一点（第一题）：我们可以通过循环预处理出所有的状态，再在动态规划的过程中判断状态是否可行，方案数累加即可。
这样来，动态规划的方程就很好推出来了（初学者可能有点困难）。
F[ I ][ j ] 表示前I行，第I行状态为J的方案数，J存的是状态，用二进制表示。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<bitset> using namespace std;//前 i 行 //当前行 状态为j的方案数 int n,m,a[15][15],g[1<<12],f[15][1<<12],mod=1e8; int check(int x) if(!((x<<1)&x)&&!((x>>1)&x)) return 1; else return 0; int main() scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)//转化成二进制 g[i]=(g[i]<<1)+a[i][j]; for(int i=0;i<(1<<m);i++) if(check(i)&&((i&g[1])==i))//后者表示在可以种植的地方选择（全选/部分/不选)地方去种，有点子集的感觉。 f[1][i]=1; for(int i=2;i<=n;i++)//第i行 for(int j=0;j<(1<<m);j++)//第i行状态为J if(check(j)&&((j&g[i])==j)) for(int k=0;k<(1<<m);k++)//第i-1行状态为k if(check(k)&&((k&g[i-1])==k)&&(!(k&j))) f[i][j]+=f[i-1][k],f[i][j]%=mod; int ans=0; for(int i=0;i<(1<<m);i++) ans+=f[n][i],ans%=mod; printf("%d",ans%mod); return 0；
[SCOI2005]互不侵犯
https://www.lydsy.com/JudgeOnline/problem.php?id=1087
第二点（第二题）：我们可以通过DFS搜索出所有符合情况的方案记录下来再进行动态规划。
DFS过程中如果搜到行的尽头，我们就保存状态再返回，否则就进行下一步搜索。
搜索分两种状态：1.当前格子不放国王，搜索下一个格子 2.当前格子放国王，就得跳过下一个格子搜索。（代码中有特别注释）
我们先不要管在列方向上的约束，只管每一行的国王不能放在一起，每一列的国王不能放在一起那是下面要考虑的问题。
当所有满足条件的行的状态都搜索出来之后，就可以动态规了，中间剔除列上不符要求的状态。
动态规划方程也跟上题的差不多：
F[ I ][ J ] [ K ] 表示前 I 行 ，第 i 行状态为J 总共选了K个国王的方案数。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long int using namespace std; ll n,t,top,sum[2000],zt[2000],f[20][1000][300],ans;//位置 状态 选了几个 void dfs(ll z,ll s,ll ci) if(ci>=n) top++; zt[top]=z; sum[top]=s; return; dfs(z,s,ci+1);//不选 dfs(z+(1<<ci),s+1,ci+2);//选 int main() scanf("%lld%lld",&n,&t); dfs(0,0,0); for(ll i=1;i<=top;i++)f[1][i][sum[i]]=1; for(ll i=2;i<=n;i++) for(ll j=1;j<=top;j++) for(ll k=1;k<=top;k++) if(zt[j]&zt[k])continue; if((zt[j]<<1)&zt[k])continue; if((zt[k]<<1)&zt[j])continue; for(ll q=sum[j];q<=t;q++) f[i][j][q]+=f[i-1][k][q-sum[j]]; //前i行 第i行状态为j 有q个国王的方案数。 for(ll i=1;i<=top;i++) ans+=f[n][i][t]; printf("%lld",ans); return 0;
嗯，这道题是右上角的大佬教我的。
我对于状压DP的理解刚刚入门，可能还有很多说的不妥当的地方希望各位神犇评论告知。
2018-07-28
19:17:14
dp状压dp
二进制的力量状态压缩DP愤怒的小鸟第一次接触状态压缩DP是在NOIP2016的愤怒的小鸟，当时菜得连题目都没看懂，不过现在回过头来看还是挺简单的，那么我们再来看看这道题吧。题意&数据范围看这考虑预处理出两个点构成的... 查看详情
p2704[noi2001]炮兵阵地(状压dp)(代码片段)
P2704[NOI2001]炮兵阵地(状压dp)第一在想压一行怎么递推。结果发现没发递推。因为影响的状态有两行。没想到01年就有压多行的操作，我老了。因此自然地就有dp[pre][now][i]dp[pre][now][i]dp[pre][now][i]iii表示当前第iii行，nownownow当... 查看详情
状压dp(代码片段)
这几天都在学习状压DP，总结一下，首先是状压DP的工具。类型符号规则例子按位与&同1为1，其余为09 00001001&5 000001011 &nb 查看详情
simplestringproblem（状压dp）(代码片段)
SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情
动态规划---状压dp2(代码片段)
今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情
poj2288islandsandbridges（状压dp）题解(代码片段)
题意：n个点，m有向边，w[i]表示i的价值，求价值最大的哈密顿图（只经过所有点一次）。价值为：所有点的w之和，加上，每条边的价值=w[i]*w[j]，加上，如果连续的三个点相互连接的价值=w[i]*w[j]*w[k]。n<=13。思路：dp[state][i][j]... 查看详情
状压dp之学校食堂(代码片段)
题目传送们小F的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表... 查看详情
dp-状压dp(代码片段)
...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍：状态表示： 转移方程：i是当前节点，j是下一步要走的节点 子集枚举：核心代码：1。由当前枚举未知首先枚举状态，枚举S中包含的节点：枚... 查看详情
tsp问题之状压dp法(代码片段)
首先,我们先来认识一下什么叫做TSP问题旅行商问题，即TSP问题（TravelingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限... 查看详情
最小总代价状压dp(代码片段)
描述n个人在做传递物品的游戏,编号为1-n。游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。即物品只能经过同一个人一次，而且每次传... 查看详情
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。初始化... 查看详情
状压dp(代码片段)
P2915[USACO08NOV]MixedUpCowsGdfs去做#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#definelllonglongusingnamespacestd;intb[25],n,m,a[25];llcnt;voiddfs(intt,int 查看详情
poj3254(状压dp）(代码片段)
CornFieldsTimeLimit:2000MS MemoryLimit:65536KTotalSubmissions:19518 Accepted:10243DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedofMbyN(1≤M≤12;1≤N≤12)squareparcels.Hewant 查看详情
b.littleponyandharmonychest(状压dp)(代码片段)
B.LittlePonyandHarmonyChest(状压dp)考虑bi≥59b_i\\ge59bi≥59时，bi=1b_i=1bi=1更优。所以只需考虑bi≤59b_i\\le59bi≤59。又因为bbb数组两两互质。即每个质因子只能被一个数使用。且≤59\\le59≤59的质因子只有161616个。考虑... 查看详情
poj3254（状压dp）(代码片段)
CornFieldsTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 20975 Accepted: 10998DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedof M by 查看详情
dp--状压dp(代码片段)
ProblemDescription互不侵犯在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。Analysisofideas把每一行的每一个状态用一个... 查看详情
flashingfluorescents(状压dp)(代码片段)
FlashingFluorescents时间限制: 1Sec 内存限制: 128MB提交: 56 解决: 19[提交][状态][讨论版][命题人:admin]题目描述Youhavenlights,eachwithitsownbutton,inaline.Pressingalight’sbuttonwilltoggl 查看详情
cf580dkefaanddishes状压dp(代码片段)
WhenKefacametotherestaurantandsatatatable,thewaiterimmediatelybroughthimthemenu.Therewerendishes.Kefaknowsthatheneedsexactlymdishes.Butatthat,hedoesn‘twanttoorderthesamedishtwicetotasteasmanydishesasp 查看详情