（最近做到了状压dp的题目，自己不会，于是学习了一手）
一、取出x的第i位：y = ( x>> ( i-1 ) ) & 1
二、将x的第i位取反：x = x ^ ( 1<< ( i-1 ) )
三、将x的第i位变为1：x = x | ( 1<< ( i-1 ) )
四、将x的第i位变成0：x = x & ~（ 1<< ( i-1 ) ）
五、将x最靠右的1变成0：x = x & (x-1)
六、取出最靠右的1：y=x&(-x)
七、把最靠右的0变成1: x | = (x-1)
何为状压dp，顾名思义就是： 状态压缩+动态规划 。既然是dp那么最为重要的就是找到状态转移方程然后转移就行。不同的在于状压dp利用二进制把状态记录成二进制数。
具体的做法就看后面的例题慢慢体会吧QWQ
这道题目是一个状压的引入和理解，没有涉及dp。
题目链接： 关灯问题
分析：考虑状态压缩，可以把灯的开和关视作1和0，则用一串01串（二进制）表示这一串灯的一个总的状态。 因为这个01串是而进制，所以他们所对应的10进制数最大不会超过（2<<10）-1=1023 也就是说最多有1023种状态，所以当然是可行的。
现在你会发现一点，就是状态压缩只适用于小数据的范围，因为这个二进制数的长度超过64，unsigned long long都存不下啦。
那么这题就可以直接广搜暴利解决，利用之前的计算方法，开灯（1）就是把对应的那一位0变成1：x|=1<<(i-1),如果本身是1的话当然没有任何影响。 同理，关灯（-1）的话就是把对应的那一位1变成0：x=x&~(1<<(i-1)),当然如果本身是0 ，也没有影响啦。
AC Code
#include<bits/stdc++.h> using namespace std; int n,m; int a[1000][1000]; int dp[10000],vis[10000]; queue<int>q; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); int siz=0; for(int i=1;i<=n;i++) siz=siz<<1|1; vis[siz]=1; q.push(siz); int flag=0; while(!q.empty()) { int now=q.front(); q.pop(); int ans=now; for(int i=1;i<=m;i++) { now=ans; for(int j=1;j<=n;j++) { if(a[i][j]==-1) now=now|(1<<(j-1)); else if(a[i][j]==1) now=now&~(1<<(j-1)); } if(vis[now]==0) { q.push(now); dp[now]=dp[ans]+1; vis[now]=1; if(now==0) { flag=1; printf("%d\n",dp[0]); break; } } } } if(flag==0) printf("-1\n"); system("pause"); return 0; }题目链接： Corn Fields
分析： 我们可以用1表示种了草，用0表示没有种草，所以每一行的状态都可以描述出来。 n和m的大小为12。故每一行的二进制状态就是2的12次方，也就是4000左右。每一行的每个状态我们都可以用上一行的满足条件的状态转移过来。
问题是怎么判断状态合不合法：
1、同一行有没有相邻的土地种植了草？ 直接左移一格（或右移一格）与原状态求交集，为空集则合法。
2、有没有把草种植在贫瘠的土壤上？ 把原有土地的状态表示出来，0为贫瘠，1为肥沃，存下每一行的土地状态。将该状态与这一行的土地状态求一下交集，如果等于原状态，则合法。
3、上下两行之间有两格土地连一起怎么办？ 在dp状态转移时候，需要枚举上一行的状态，这个时候再进行判断。
AC Code
#include<bits/stdc++.h> using namespace std; const int MOD=1e8; int m,n;//m行n列 int a[14][14],f[14],ans[1<<12]; int dp[14][1<<12]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); f[i]=(f[i]<<1)|a[i][j];//记录每一行的土地状态 } } int siz=1<<n; for(int i=0;i<siz;i++) if(!(i&(i<<1))&&!(i&(i>>1))) ans[i]=1;//预处理一行中哪些状态是可行的 dp[0][0]=1; for(int i=1;i<=m;i++) { for(int j=0;j<siz;j++) { if(ans[j]&&(f[i]&j)==j)//解决问题1和2 { for(int k=0;k<siz;k++)//枚举上一行的状态 if(!(k&j)) dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD; } } } int res=0; for(int i=0;i<siz;i++) res=(res+dp[m][i])%MOD; printf("%d\n",res); system("pause"); return 0; }题目链接 互不侵犯
题意： 给定一个n*n的棋盘。在上面放k个王。满足这k个王无法相互攻击。王可以攻击他相邻的8个格子。
思路： 相当于上一题的一个加强板，开三个维度来存储dp的状态（因为题目里面有两个要求：n行和固定了要求拜访的棋子个数，剩下一个维度是状压的状态） dp[ i ][ j ][ k ]表示第i行，这一行国王摆放的状态为j，已经摆放了k个国王的方案数。
AC Code
#include<bits/stdc++.h> using namespace std; long long maze[10][1<<10][100];//记得要开long long int f[1<<10],num[1<<10]; int check(int a,int b) {//判断上下两行是否合法 if((a<<1)&b) return 0; if((a>>1)&b) return 0; if(a&b) return 0; return 1; } int main() { int n,m; scanf("%d%d",&n,&m); int siz=1<<n; for(int i=0;i<siz;i++) {//预处理一行里有哪些状态是可行的 if(!(i&(i<<1))&&!(i&(i>>1))) { f[i]=1; int tmp=i; while(tmp)//预处理每种状态的国王数量 { if(tmp&1) num[i]++; tmp=tmp>>1; } } } for(int i=0;i<siz;i++)//由于第一行上面没有格子，所以需要单独处理 if(f[i]) maze[1][i][num[i]]=1; for(int i=2;i<=n;i++) {//枚举第几行 for(int j=0;j<siz;j++)//枚举这一行的状态 { if(!f[j]) continue; for(int k=0;k<siz;k++)//枚举上一行的状态 { if(!check(k,j)||!f[k]) continue; for(int l=m;l>=num[j];l--) { maze[i][j][l]+=maze[i-1][k][l-num[j]]; } } } } long long ans=0; for(int i=0;i<siz;i++) ans+=maze[n][i][m]; printf("%lld\n",ans); system("pause"); return 0; }题目链接 Problem Arrangement
题意： 输入n和m，接下来一个n*n的矩阵，a[i][j]表示第i道题放在第j个顺序做可以加a[i][j]的分数，问做完n道题所得分数大于等于m的概率。用分数表示，分母为上述满足题意的方案数，分子是总的方案数,输出最简形式。
思路： 由于n很小，可以想到用状压dp来解决。因为最多只有12道题，对于每一道题我们可以枚举所有位置，看看哪个位置可以放这个题。dp[i][j]表示在i状态下得分为j的方案数,具体实现看代码。
#include<bits/stdc++.h> using namespace std; int casen; int n,m; int a[15][15]; int dp[(1<<13)+10][510]; int f[15]; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int main() { f[1]=1; for(int i=2;i<=12;i++)//计算阶层 f[i]=f[i-1]*i; scanf("%d",&casen); while(casen--) { memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); dp[0][0]=1; for(int i=0;i<(1<<n);i++) { int cnt=0; for(int j=1;j<=n;j++) { if(((1<<(j-1))&i)>0)//判断i的二进制下第j为是否为1 cnt++; } for(int j=1;j<=n;j++)//看看可以由i状态转移到哪些别的状态 { if(((1<<(j-1))&i)>0) continue; for(int k=0;k<=m;k++) { if(k+a[cnt+1][j]>=m) dp[i+(1<<(j-1))][m]+=dp[i][k]; else dp[i+(1<<(j-1))][k+a[cnt+1][j]]+=dp[i][k]; } } } if(dp[(1<<n)-1][m]==0) puts("No solution"); else { int g=gcd(f[n],dp[(1<<n)-1][m]); printf("%d/%d\n",f[n]/g,dp[(1<<n)-1][m]/g); } } //system("pause"); return 0; }题目链接： 炮兵阵地
题意：
有一块n*m的土地，上面有平原有山地，炮兵只能布置在平原地区，每个炮兵阵地的攻击范围是一个十字架形状（具体看题目），每个炮兵阵地不能设置在别的炮兵阵地的攻击范围内，问最多能设置多少个炮兵阵地。
思路： 定义：dp[i][j][k]表示到第i行状态为k，且上一行状态为j的最大方案数。
初始化：然后我们来考虑初始化，因为状态肯定由前两行推过来，所以我们需要单独处理第一二行的方案数。
转移方程：i为当前行，j为上一行的状态，k为当前行的状态，p为上上行的状态。 dp[i][j][k] = max ( dp[i][j][k]，dp[i-1][p][j] +当前行的炮兵数量 )
但是后来看了数据你会发现 第一维数据到100，第二维第三维的数据是1<<10=1024。很显然空间会炸。 于是（通过看别人的题解我发现qaq），因为炮兵阵地左右两格内都应该为0，所以也没有几种情况是满足横排的（m=10时才70个不到），我们可以把满足横排的情况用新的数组记录下来，后面二维于是就可以压到70*70。
这样就可以过了，但是还有很多人用到了滚动数组，想看的可以到洛古的题解里找。
代码注释还是很详细的qaq，细节就不多说了。
#include<bits/stdc++.h> using namespace std; int n,m,k; int s[1005],g[1005]; int f[102][1005][1005],ans; char ma[103]; int mapp[103]; int get(int x) { int e=0; while(x) { e++; x-=x&(-x); } return e; } int main() { cin>>n>>m; for(int i=1;i<=n;i++)//读入地图，将山地设为1 { scanf("%s",ma); for(int j=0;j<m;j++) if(ma[j]=='H') mapp[i]=mapp[i]+(1<<j);//记录下每一行的状态 } for(int i=0;i<(1<<m);i++)//枚举所有状态 if(((i&(i<<1))==0)&&((i&(i<<2))==0)&&((i&(i>>1))==0)&&((i&(i>>2))==0))//判断每一行是否存在冲突 { k++; s[k]=i; g[k]=get(i); if((i&mapp[1])==0) f[1][0][k]=g[k];//初始化第一行 } //初始化第二行 for(int i=1;i<=k;i++)//枚举第一行的状态 for(int j=1;j<=k;j++)//枚举第二行的状态 if(((s[i]&s[j])==0)&&((s[j]&mapp[2])==0)) f[2][i][j]=max(f[2][i][j],f[1][0][i]+g[j]); for(int i=3;i<=n;i++)//枚举当前行数 for(int j=1;j<=k;j++)//枚举当前行数状态 if((mapp[i]&s[j])==0)//不与地形冲突 for(int p=1;p<=k;p++)//枚举前一行的状态 if((s[p]&s[j])==0)//当前状态不与前一行冲突 for(int q=1;q<=k;q++)//枚举前两行 //不与前两行冲突且前两行自身不冲突 if(((s[q]&s[p])==0)&&((s[q]&s[j])==0)) f[i][p][j]=max(f[i][p][j],f[i-1][q][p]+g[j]); for(int i=1;i<=k;i++)//枚举最后两行结尾的情况，统计答案 for(int j=1;j<=k;j++) ans=max(f[n][i][j],ans); cout<<ans; system("pause"); return 0; }觉得有用的话就点个赞再走吧QWQ
