狀壓這個和二進制分不開關系

所以，對于二進制的熟悉是必不可少的技能

&  與操作,，1不變,，0變0    

|  或操作，0不變,，1變1　　

^  異或操作,0不變,，1取反 　　

～ 取反操作，把每一個二進制位0變1,，1變0

還有一些復雜操作可以根據這些去理解

狀態(tài)壓縮

所謂狀態(tài)壓縮就是把dp的每一次轉移時的狀態(tài)用二進制來表示

或者用二進制來間接表示

比如

這里有10個蘋果,，編號1-10

我拿走了1,4,7,9這四個蘋果

那么我們可以用011011010這一串二進制數來表示現在的狀態(tài)

0表示這個位置沒有蘋果,，1表示有

那么這就是一個狀態(tài)

相比拿一個bool型的數組,，這樣表示更方便,，內存更小，操作更簡單

現在我想把拿走的蘋果放回去,，沒拿走的拿走

那么狀態(tài)就變成100100101

直接取反      a=011011010   b=100100101

a==～b;

這時候就充分展示了狀態(tài)壓縮的快捷性

下面我們講一道例題,。。,。,。。

在n*n(n≤20)的方格中放置n個車,，每個車可以攻擊所在的行和列,，求方案總數

直接上排列組合，n,！,，很好理解啊

在n*n(n≤20)的方格棋盤上放置n 個車，某些格子不能放,，求使它們不能互相攻擊的方案總數,。

這時候一些格子不能放，就要考慮每一行的情況

但是   ,，,，，,，即使每一行中有的格子不能放,，最終還是每一行每一列都要有一個車子

所以我們用s這個int型的數來表示現在的狀態(tài)（行狀態(tài)）

如果這一列現在有車子，那這一位就是1

所以最終s一定會變成11111111111（全是1）只有這樣才能把n個車全部放進去

這樣這一狀態(tài)有幾個車子說明這就是第幾行

那這樣轉移方程就有了

dp[s]+=dp[s^(s&-s)];

for(;j>0;j-=(j&-j)){
    dp[i]+=dp[i^(j&(-j))];
}

還有個問題,，有些格子不能放車

這怎么辦,？？,？,？？,？,？？,？,？？

還記得前面的蘋果嗎

用1表示這里能放車子,，0表示不可以

在狀態(tài)轉移的時候&一下就可以啦

j=i&s[num];

代碼如下

#include<bits/stdc++.h>
#define ll long long
using 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就結束了

也許你已經發(fā)現了

所有的n都小于等于20

因為int只有32位

這也是狀壓的前提

所以當你一直為空間時間復雜度著急時

就去考慮狀壓

而狀壓前先找到可以狀壓的數

就是32位以內的

over