前言
状态压缩是一种(dp)里的暴力，但是非常优秀，状态的转移，方程的转移和定义都是状压(dp)的难点，本人在次总结状压dp的几个题型和例题，便于自己以后理解分析状态和定义方式
状态压缩动态规划，就是我们俗称的状压(dp)，是利用计算机二进制的性质来描述状态的一种(dp)方式。
很多棋盘问题都运用到了状压，同时，状压也很经常和BFS及(dp)连用。
状压(dp)其实就是将状态压缩成2进制来保存 其特征就是看起来有点像搜索，每个格子的状态只有(1)或(0) ，是另一类非常典型的动态规划
NO.1 Corn Fields G
题目描述
农场主(John)新买了一块长方形的新牧场，这块牧场被划分成(M)行(N)列((1 le M le 12; 1 le N le 12))，每一格都是一块正方形的土地。(John)打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是(John)不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
(John)想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
输入格式
第一行：两个整数(M)和(N)，用空格隔开。
第(2)到第(M+1)行：每行包含(N)个用空格隔开的整数，描述了每块土地的状态。第(i+1)行描述了第(i)行的土地，所有整数均为(0)或(1)，是(1)的话，表示这块土地足够肥沃，(0)则表示这块土地不适合种草。
输出格式
一个整数，即牧场分配总方案数除以(100,000,000)的余数。
输入输出样例
输入 #1
2 3
1 1 1
0 1 0
输出 #1
9
分析
首先看到范围，(M)和(N)的范围都极小，所以根据状压(dp)通性，显然要通过每行或者每一列的状态来进行转移。这个题比较灵性（恶心）的就是行为(M)，颠覆认知……因为每个奶牛不能挨在一起，并且不种植也是一种方案，所以合法的状态肯定是要初始化一下的，即：
g[i]=(!(i<<1)&i&&!(i&(i>>1)))
这道题就是按每一行来进行状态转移，定义(f[i][j])为第(i)行状态为(j)时的方案数，所以要从上一行转移而来，那么设上一行的状态为(k),所以就可以根据这个列出状态转移方程：
最终的答案就是把最后一行每一个状态的答案加起来即可
具体的初始化见代码注释
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 13;
const int mod = 100000000;
int n,m;
int jl[maxn][maxn];
int f[maxn][1<<maxn];
int ste[maxn],g[1<<maxn];
int main(){
cin>>m>>n;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
cin>>jl[i][j];//记录矩阵
}
}
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
ste[i] = (ste[i]<<1)+jl[i][j];//用二进制记录每一行的状态（有草的地方）
}
}
f[0][0] = 1;
int ms = 1<<n;//总状态
for (int i = 0; i <ms; i++)
g[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);//初始化出所有状态中的合法状态
for(int i=1;i<=m;++i){//枚举每一行
for(int j=0;j<ms;j++){//当前行状态
if(g[j] && (j & ste[i]) == j){//该状态合法且当前放牛都是在有草的地方
for(int k=0;k<ms;k++){//上一行状态
if((k&j) == 0){//上一行与这一行不能有相同的状态，也就是牛不能相邻
f[i][j] = (f[i][j]+f[i-1][k])%mod;
}
}
}
}
}
int ans = 0;
for(int i=0;i<ms;++i){//累加每一个状态的方案
ans =(ans+f[m][i])%mod;
}
cout<<ans%mod<<endl;//记得每一次都要取模
return 0;
}
NO.2 No Change G
题目
约翰到商场购物，他的钱包里有(K(1 le K le 16))个硬币，面值的范围是(1..100,000,000)。
约翰想按顺序买 (N)个物品((1 le N le 100,000))，第(i)个物品需要花费(c_i)块钱，((1 le c_i le 10,000))。
在依次进行的购买(N)个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。
请计算出在购买完(N)个物品后，约翰最多剩下多少钱。如果无法完成购买，输出(-1)
输入格式
-
Line (1): Two integers, (K) and (N).
-
Lines (2..1+K): Each line contains the amount of money of one of FJ's coins.
-
Lines (2+K..1+N+K): These (N) lines contain the costs of FJ's intended purchases.
输出格式
- Line 1: The maximum amount of money FJ can end up with, or -1 if FJ cannot complete all of his purchases.
输入输出样例
输入 #1
3 6
12
15
10
6
3
3
2
3
7
输出 #1
12
说明/提示
FJ has (3) coins of values (12, 15), and (10). He must make purchases in sequence of value (6, 3, 3, 2, 3), and (7).
FJ spends his 10-unit coin on the first two purchases, then the 15-unit coin on the remaining purchases. This leaves him with the 12-unit coin.
分析
看到友好又有标志性的硬币数的范围，当然要从硬币使用作为状态来进行状压啦！所以我们的状态就定义为(f[i])表示使用硬币状态为(i)的时候买的最大物品数，看题意大概就是买东西需要按顺序，所以我们维护一个前缀和来优化时间效率，并且记录一下所有硬币的价值总和，方便最后判断。与上一个题相似的是，也要把使用每个硬币的状态提前初始化一下：
表示的是只用了第(i)个硬币的状态。并且(g[1]=1)然后就可以愉快的状态转移了！状态转移就是用了状态为(i的)硬币时买的物品，与当前用了第(j)个硬币买的物品去最大值。状态转移方程比较特殊，所以一会在代码中解释。
状态转移完了就需要统计答案了，每次当前状态能买的最大物品为(n)时就开始统计。枚举硬币，如果当前状态用了该硬币，那么就让计数(cnt)加上当前硬币的价值，最后(ans)取最大的剩余价值。需要注意的是最后剩余可以为(0)，所以(ans)应该初始化为(-1)，如果小于(0)，那么就是不可能的情况。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int mm = 19;
int f[1<<mm];
int n,k;
int sum[maxn];
int g[maxn];
int tot,cnt,ans = -1;
int c[mm],a[maxn];
int main(){
cin>>k>>n;
for(int i=1;i<=k;++i){//输入硬币数并计算总价值
cin>>c[i];
tot += c[i];
}
for(int i=1;i<=n;++i){//输入每个物品价值并求出前缀和
cin>>a[i];
sum[i] = sum[i-1]+a[i];
}
g[1] = 1;
for(int i=2;i<=k;++i){//初始化每个硬币使用的状态
g[i] = g[i-1]<<1;
}
int ms = (1<<k)-1;
for(int i=0;i<=ms;++i){//枚举所有状态
for(int j=1;j<=k;++j){//枚举所有硬币
if(i & g[j]){//当前状态用了该硬币就继续运行
int te = f[i^g[j]];//te为没用该硬币时能卖的商品数。
te = upper_bound(sum+1,sum+n+1,sum[te]+c[j])-sum;//二分求使用了第j个硬币后大于的第一个商品前缀和，就可以统计出能卖多少商品。
f[i] = max(f[i],te - 1);//此时te-1为买了的商品数，取max更新
}
}
}
for(int i=0;i<=ms;++i){//再次枚举状态
if(f[i] == n){//当前状态能够买完n个物品就继续进行
cnt = 0;
for(int j=1;j<=k;++j){
if((i & g[j])){//当前状态用了第j个硬币就加上它的价值
cnt += c[j];
}
}
ans = max(ans,tot-cnt);//求出最大的剩余价值
}
}
if(ans<0)cout<<-1<<"
";//小于0就是不可能买完
else cout<<ans<<endl;
}
NO.3 吃奶酪
题目描述
房间里放着 (n) 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 ((0,0)) 点处。
输入格式
第一行有一个整数，表示奶酪的数量 (n)。
第 (2) 到第 ((n+1)) 行，每行两个实数，第 ((i+1)) 行的实数分别表示第 (i) 块奶酪的横纵坐标 (x_i, y_i)。
输出格式
输出一行一个实数，表示要跑的最少距离，保留 (2) 位小数。
输入输出样例
输入 #1
4
1 1
1 -1
-1 1
-1 -1
输出 #1
7.41
说明/提示
数据规模与约定
对于全部的测试点，保证 (1le nle 15)，(|x_i|,|y_i| le 200)，小数点后最多有 (3) 位数字。
提示
对于两个点 ((x_1,y_1))，((x_2, y_2))，两点之间的距离公式为 (sqrt{(x_1-x_2)^2+(y_1-y_2)^2})。
分析
再一次看到友好的奶酪数据范围，显然要从吃奶酪的状态入手转移，因为需要计算距离，所以我们需要把每个点之间的距离全部求出来，并且状态数组需要一维来存储上一次的位置，所以我们定义(f[i][j])为吃奶酪状态(i)时位置为(j)的走的距离，也就是吃了奶酪(j)，从上一个状态没吃(j)转移来,位置为(k)。所以状态转移方程就是：
(jl)就是距离……
而我们需要预处理一些东西，每个位置之间距离是一个，原点与每个位置之间距离也要预处理，然后就是只吃了一个奶酪的走的长度预处理，然后就可以愉快的状态转移了。最后不要忘了把每个位置吃完奶酪的走的距离都扫一边。
代码
#include<bits/stdc++.h>
using namespace std;
#define db double
const int maxn = 16;
double dp[1<<maxn][maxn];
int n;
db jl[maxn][maxn];
db jlx[maxn],jly[maxn];
db pow(db x){//求乘方
return x*x;
}
db len(db xx,db yy,db x2,db y2){//求距离
return sqrt(pow(xx-x2)+pow(yy-y2));
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>jlx[i]>>jly[i];
jl[0][i] = jl[i][0] = len(0,0,jlx[i],jly[i]);//原点到每个点的距离
}
for(int i=1;i<=n;++i){//每个位置之间的距离
for(int j=1;j<=n;++j){
jl[i][j] = len(jlx[i],jly[i],jlx[j],jly[j]);
}
}
for(int i=1;i<(1<<n);++i){//初始化极大值
for(int j=1;j<=n;++j){
dp[i][j] = 999999.0;
}
}
for(int i=1;i<=n;++i){//只吃了一个奶酪的距离
dp[1<<(i-1)][i] = jl[0][i];
}
dp[0][0] = 0.0;
for(int i=0;i<(1<<n);++i){//枚举状态
for(int j=1;j<=n;++j){
if((i & (1<<(j-1))) == 0)continue; //没吃第j个就continue
for(int k=1;k<=n;++k){
if(k == j)continue;//上个位置和这个位置相同无意义，continue
if((i & (1<<(k-1))) == 0)continue;//没吃第k个也没意义，continue
dp[i][j] = min(dp[i][j],dp[i - (1<<(j-1))][k] + jl[k][j]);//状态转移
}
}
}
db ans = 99999999.0;//一定是浮点数
for(int i=1;i<=n;++i){//从头到尾扫一边
ans = min(ans,dp[(1<<n)-1][i]);
}
printf("%.2lf",ans);
}
NO.4 中国象棋
题目描述
这次小可可想解决的难题和中国象棋有关，在一个(N)行(M)列的棋盘上，让你放若干个炮（可以是(0)个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！
输入格式
一行包含两个整数(N)，(M)，之间由一个空格隔开。
输出格式
总共的方案数，由于该值可能很大，只需给出方案数模(9999973)的结果。
输入输出样例
输入 #1
1 3
输出 #1
7
说明/提示
样例说明
除了(3)个格子里都塞满了炮以外，其它方案都是可行的，所以一共有(2 imes 2 imes 2-1=7)种方案。
数据范围
(100\%)的数据中(N)和(M)均不超过(100)
(50\%)的数据中(N)和(M)至少有一个数不超过(8)
(30\%)的数据中(N)和(M)均不超过(6)
分析
其实这个题像极了线性dp，但是思想跟状压有一丢丢相似
想必大家都知道象棋规则吧，不知道的可以去问问度娘，按照象棋的规则，一行或者一列里最多有两个炮，所以就可以根据这个来转移了。
而且每一行也最多放两个，所以就可以一一枚举进行转移，方程过多，在这里就不列举出来了，具体见代码注释吧。
(f[i][j][k])表示第(i)行
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 101;
const int Mod = 9999973;
int n,m;
long long f[maxn][maxn][maxn];
int Pow(int num){
return num*(num-1)/2;
}
int main(){
ios::sync_with_stdio(false);//cin/cout优化，加不加无所谓……
cin.tie(0);
cin>>n>>m;
f[0][0][0] = 1;
for(int i=0;i<n;++i){//枚举行
for(int j=0;j<=m;++j){//枚举有一个棋子的列数
for(int k=0;j+k<=m;++k){//两个棋子的列数
if(f[i][j][k]){//上一次状态不为0才转移
f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%Mod;//不放棋子
if(m-k-j>=1)f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k]*(m-k-j))%Mod;//在没放棋子的列放一个
if(j>=1)f[i+1][j-1][k+1]=(f[i+1][j-1][k+1]+f[i][j][k]*j)%Mod;//在放了一个棋子的列放一个
if(m-k-j>=2)f[i+1][j+2][k]=(f[i+1][j+2][k]+f[i][j][k]*Pow(m-k-j))%Mod;//在没放棋子的列分别放两个
if(m-k-j>=1 && j>=1)f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k]*(m-k-j)*j)%Mod;//放了一个棋子和没放棋子的列各放一个
if(j>=2)f[i+1][j-2][k+2]=(f[i+1][j-2][k+2]+f[i][j][k]*Pow(j))%Mod;//在放了一个棋子的列各放一个
}
}
}
}
long long ans= 0;
for(int i=0;i<=m;++i){
for(int j=0;i+j<=m;++j){//统计答案
ans=(ans+f[n][i][j])%Mod;
}
}
cout<<ans<<"
";
}/*最后搞个总结，每次从上个状态转移而来，如果放了一个棋子，一定要乘以剩下能放棋子列的个数，放两个当然是要乘以组合数了，这样才能求出方案数*/