状态压缩利用二进制枚举每一种状态，用0和1表示取或不取，然后通过位运算实现。例如，现在有20个物品，分别用一个数在二进制下20位表示取或不取，例如，10在二进制下位1010，即代表选取第2和4个物品。对一个数x，判断第i个物品是否被选取可以用位运算(1<<i)&x判断。状态压缩通常伴随dp一起出现，是一种时间复杂度很高很暴力的算法。
经典例题：hdu1565方格取数
http://acm.hdu.edu.cn/showproblem.php?pid=1565
给一个n*n的方阵，取若干个数，要求任意两个数所在方格不相邻，求取出数的最大和。
首先预处理出每行的取数方案，对于i，用1代表取，0代表不取，若(i>>1)&i为0，即代表i方案可以被选用，因为相邻两项不存在同为1的。
然后对于每行，枚举该行选取方案，对上一行枚举方案枚举，若两方案与值为0则可以转移，因为此时没有同一列的被选取。自上而下转移即可。
贴上AC代码。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int,int> pii; #define rep(i,x,y) for(int i=x;i<y;i++) #define rept(i,x,y) for(int i=x;i<=y;i++) #define per(i,x,y) for(int i=x;i>=y;i--) #define pb push_back #define mp make_pair #define fi first #define se second #define de(x) cout<< #x<<" = "<<x<<endl #define dd(x) cout<< #x<<" = "<<x<<" " #define mes(a,b) memset(a,b,sizeof a) const int inf= 0x3f3f3f3f; int way[1<<15],cnt=0; int matrix[25][25]; int dp[25][1<<15]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; for(int i=0;i<(1<<20);i++) if((i&(i>>1))==0) way[cnt++]=i; // de(cnt); // de((1<<15)); while(cin>>n) { mes(dp,0); rept(i,1,n) rept(j,1,n) cin>>matrix[i][j]; rept(i,1,n) { rep(j,0,cnt) { if((1<<n)<=way[j]) break; int sum=0,choose=way[j],p=1; while(choose) { if(choose&1) sum+=matrix[i][p]; p++; choose>>=1; } // dd(i);dd(j);de(sum); dp[i][j]=0; rep(k,0,cnt) { if((1<<n)<=way[k]) break; if((way[j]&way[k])==0) { // dd(j);de(k); dp[i][j]=max(dp[i][j],dp[i-1][k]+sum); } } } } int ans=0; rep(i,0,cnt) { // dd(i); if((1<<n)<=way[i]) break; ans=max(ans,dp[n][i]); } cout<<ans<<" "; } return 0; }