状压dp的核心在于，当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时，我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····此时熟悉相关的位运算就很重要了····以下是常见的一些需要位运算方法
然后说实话状压dp其它方面就和普通dp差不多了···它不像数位区间树形那样或多或少好歹有自己一定套路或规律····如何想到转移方程和状态也就成了其最难的地方···
例题：
1.Corn Fields（poj3254）
Description
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
Input
Lines 2..M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)
Output
Sample Input
2 3 1 1 1 0 1 0
Sample Output
9
Hint
1 2 3
4
There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> using namespace std; const int N=15; const int mod=1e+8; int f[N][5000],map[N],n,m,ans,maxx; inline int R() { char c;int f=0; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c<='9'&&c>='0';c=getchar()) f=(f<<3)+(f<<1)+c-'0'; return f; } inline void solve() { for(int i=0;i<maxx;i++) if(((i|map[1])==map[1])&&!(i&(i>>1))) f[1][i]=1; for(int i=2;i<=n;i++) for(int j=0;j<maxx;j++) if(f[i-1][j]) for(int k=0;k<maxx;k++) if(((k|map[i])==map[i])&&!(k&(k>>1))&&!(k&j)) f[i][k]=(f[i][k]+f[i-1][j])%mod; for(int i=0;i<maxx;i++) ans=(ans+f[n][i])%mod; } int main() { //freopen("a.in","r",stdin); n=R(),m=R();int a;maxx=(1<<m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a=R(); if(a) map[i]|=(1<<(j-1)); } solve(); cout<<ans<<endl; return 0; }
2.互不侵犯king（bzoj1087）
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
Sample Output
f[i][j][now]=∑f[i-1][j-cnt[now]][q]；
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> #include<cstdlib> using namespace std; int cnt[600],n,k,maxx; long long f[10][600][100],ans=0; bool jud1[600],jud2[600][600]; inline void pre() { for(int i=0;i<=maxx;i++) for(int j=0;j<n;j++) if(i&(1<<j)) cnt[i]++; for(int i=0;i<=maxx;i++) if(!(i&(i>>1))) jud1[i]=true; for(int i=0;i<=maxx;i++) for(int j=0;j<=maxx;j++) if((!(i&j))&&(!(i&(j>>1)))&&(!(i&(j<<1)))) jud2[i][j]=true; } inline void dp() { for(int i=0;i<=maxx;i++) if(jud1[i]) f[1][i][cnt[i]]=1; for(int i=2;i<=n;i++) //枚举行 for(int j=0;j<=maxx;j++) //枚举上一状态 if(jud1[j]) for(int r=0;r<=maxx;r++) //枚举该行状态 if(jud1[r]&&jud2[j][r]) for(int l=cnt[r];l<=k;l++) //枚举总数量 f[i][r][l]=f[i][r][l]+f[i-1][j][l-cnt[r]]; for(int i=0;i<=maxx;i++) ans+=f[n][i][k]; } int main() { scanf("%d%d",&n,&k);maxx=(1<<n)-1; pre(); dp(); cout<<ans<<endl; return 0; }
3.奇怪的道路（bzoj3195）
Description
小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达，交通方面也不例外。考古学家已经知道，这个文明在全盛时期有n座城市，编号为1..n。m条道路连接在这些城市之间，每条道路将两个城市连接起来，使得两地的居民可以方便地来往。一对城市之间可能存在多条道路。
据史料记载，这个文明的交通网络满足两个奇怪的特征。首先，这个文明崇拜数字K，所以对于任何一条道路，设它连接的两个城市分别为u和v，则必定满足1 <=|u - v| <= K。此外，任何一个城市都与恰好偶数条道路相连（0也被认为是偶数）。不过，由于时间过于久远，具体的交通网络我们已经无法得知了。小宇很好奇这n个城市之间究竟有多少种可能的连接方法，于是她向你求助。
方法数可能很大，你只需要输出方法数模1000000007后的结果。
Input
输入共一行，为3个整数n，m，K。
Output
输出1个整数，表示方案数模1000000007后的结果。
Sample Input
3 4 1
【输入样例2】
4 3 3
Sample Output
3
【输出样例2】
4
【数据规模】
HINT
100%的数据满足1
<= n <= 30, 0 <= m <= 30, 1 <= K <= 8.
【题目说明】
两种可能的连接方法不同当且仅当存在一对城市，它们间的道路数在两种方法中不同。
在交通网络中，有可能存在两个城市无法互相到达。
哇这道题做得我心态爆炸···再次验证了状压dp没有套路···这里引用sunshinezff题解，%%%%%
因为K只有8,我们可以考虑状压dp.将i-K到i的度的奇偶性压成1维.
设f[i][j][k][l]表示考虑到点i,用了j条边,i-K到i的奇偶性为k,当前处理i-K+l和i之间的连边。
如果这条边不连,可以转移到f[i][j][k][l+1].
如果这条边连,可以转移到f[i][j+1][k^(1<<K)^(1<<l)][l].
如果l=K并且i-K的度为偶数,可以转移到f[i+1][j][k>>1][0];
最后答案就是f[n+1][m][0][0];
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> using namespace std; int f[35][35][1<<9][9]; const int mod=1e9+7; int n,m,K,maxx; int main() { //freopen("a.in","r",stdin); scanf("%d%d%d",&n,&m,&K);maxx=(1<<(K+1)); f[2][0][0][0]=1; for(int i=2;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<maxx;k++) { for(int l=0;l<K;l++) if(f[i][j][k][l]) { (f[i][j][k][l+1]+=f[i][j][k][l])%=mod; if(j<m&&i-K+l>0) (f[i][j+1][k^(1<<K)^(1<<l)][l]+=f[i][j][k][l])%=mod; } if((k&1)==0&&(f[i][j][k][K])) f[i+1][j][k>>1][0]=f[i][j][k][K]; } cout<<f[n+1][m][0][0]<<endl; return 0; }
4.炮兵阵地（poj1185）
Description
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
Output
Sample Input
5 4 PHPP PPHH PPPP PHPP PHHP
Sample Output
6
Source
f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+cnt[i])
其中l为枚举的上上一行···注意情况要合法··
另外后两维直接表示状态会爆空间···因此注意用hash表存储·····另外注意讨论n=1时的情况
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> using namespace std; int f[105][305][305],ans,ha[305],tot=0,maxx,n,m,cnt[305],ma[105]; bool jud[305][305]; char s[15]; inline void pre() { for(int i=0;i<maxx;i++) if((!(i&(i>>1)))&&(!(i&(i>>2)))) { ha[++tot]=i; int temp=0; for(int j=0;j<m;j++) if(((1<<j)&i)) temp++; cnt[tot]=temp; } for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) if(!(ha[i]&ha[j])) jud[i][j]=true; for(int i=1;i<=tot;i++) if((ha[i]|ma[1])==ma[1]) f[1][i][0]=cnt[i]; for(int i=1;i<=tot;i++) if((ha[i]|ma[1])==ma[1]) for(int j=1;j<=tot;j++) if(jud[i][j]&&(ha[j]|ma[2])==ma[2]) f[2][j][i]=max(f[2][j][i],f[1][i][0]+cnt[j]); } int main() { //freopen("a.in","r",stdin); scanf("%d%d",&n,&m);maxx=(1<<m); if(m==0||n==0) { printf("0 "); return 0; } for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=m;j++) if(s[j]=='P') ma[i]|=(1<<(j-1)); } pre(); for(int i=3;i<=n;i++) for(int j=1;j<=tot;j++) if((ma[i-2]|ha[j])==ma[i-2]) for(int k=1;k<=tot;k++) if(jud[j][k]&&(ma[i-1]|ha[k])==ma[i-1]) for(int l=1;l<=tot;l++) if(jud[l][k]&&jud[j][l]&&(ma[i]|ha[l])==ma[i]) f[i][l][k]=max(f[i][l][k],f[i-1][k][j]+cnt[l]); int ans=0; if(n!=1) { for(int i=2;i<=n;i++) for(int j=1;j<=tot;j++) if((ma[i]|ha[j])==ma[i]) for(int k=1;k<=tot;k++) if(jud[j][k]&&(ma[i-1]|ha[k])==ma[i-1]) ans=max(ans,f[i][j][k]); } else for(int i=1;i<=tot;i++) if((ha[i]|ma[1])==ma[1]) ans=max(ans,f[1][i][0]); printf("%d ",ans); return 0; }
5.愤怒的小鸟（石室oj NOIP2016）
题目背景
NOIP2016 提高组 Day2 T3
题目描述
Kiana 最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。
有一架弹弓位于 (0,0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 y=ax2+bx 的曲线，其中 a，b 是 Kiana 指定的参数，且必须满足 a＜0。
当小鸟落回地面（即x轴）时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (xi,yi) 。
如果某只小鸟的飞行轨迹经过了(xi,yi)，那么第 i 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；
如果一只小鸟的飞行轨迹没有经过(xi,yi)，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。
例如，若两只小猪分别位于 (1,3) 和 (3,3) ，Kiana 可以选择发射一只飞行轨迹为 y=-x2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。
假设这款游戏一共有 T 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。
输入格式
下面依次输入这 T 个关卡的信息。每个关卡第一行包含两个非负整数 n，m ，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 n 行中，第 i 行包含两个正实数 xi，yi ，表示第 i 只小猪坐标为 (xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果 m=0，表示 Kiana 输入了一个没有任何作用的指令。
如果 m=1 ，则这个关卡将会满足：至多用 
只小鸟即可消灭所有小猪。
如果 m=2 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 
只小猪。
保证 1≤n≤18，0≤m≤2，0＜xi,yi＜10，输入中的实数均保留到小数点后两位。
上文中，符号 
分别表示对 c 向上取整和向下取整，例如：
输出格式
对每个关卡依次输出一行答案。
输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。
样例数据 1
输入
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
输出
1
1
样例数据 2
输入
3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00
输出
2
2
3
样例数据 3
输入
1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99
输出
6
备注
【样例1说明】
这组数据中一共有两个关卡。
第一个关卡与【问题描述】中的情形相同，2 只小猪分别位于 (1.00,3.00) 和 (3.00,3.00) ，只需发射一只飞行轨迹为 y=-x2+4x 的小鸟即可消灭它们。
第二个关卡中有 5 只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y=-x2+6x 上，故 Kiana 只需要发射一只小鸟即可消灭所有小猪。
【数据规模与约定】
数据的一些特殊规定如下表：
谨以此题献给我挂成狗的NOIP2016
先预处理出g[i][j],表示打第i和j头猪时总共能打到的猪的状态·····
然后用f[i]表示打到i状态的猪时用的最少小鸟数，得出dp方程：
f[i|g[j][k]]=min(f[i|g[j][k],f[i]+1);
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> using namespace std; struct node { double x,y; }p[20]; const int inf=0x3f3f3f3f; int T,n,m,maxx; int g[20][20],f[270000]; bool jud[20][20]; double A,B; inline void Cnt(node a,node b) { double xx1=a.x*a.x,xx2=b.x*b.x; B=(a.y/xx1*xx2-b.y)/(a.x/xx1*xx2-b.x); A=(a.y/a.x*b.x-b.y)/(xx1/a.x*b.x-xx2); } inline double Abs(double a) { return a<0?-a:a; } inline void pre() { memset(f,inf,sizeof(f));memset(g,0,sizeof(g)); f[0]=0; for(int i=0;i<n;i++) f[1<<i]=1; for(int i=1;i<=n;i++) g[i][i]|=(1<<(i-1)),jud[i][i]=true; for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { if(Abs(p[i].x-p[j].x)<1e-6) continue; Cnt(p[i],p[j]); if(A>0||Abs(A)<1e-6) continue; jud[i][j]=jud[j][i]=true; for(int k=1;k<=n;k++) if(Abs(p[k].x*p[k].x*A+B*p[k].x-p[k].y)<1e-6) g[i][j]|=(1<<(k-1)); f[g[i][j]]=1; } } inline void dp() { for(int i=0;i<maxx;i++) if(f[i]!=inf) for(int j=1;j<n;j++) for(int k=j;k<=n;k++) if(jud[j][k]) f[i|g[j][k]]=min(f[i|g[j][k]],f[i]+1); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m);maxx=(1<<n); for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); pre(); dp(); cout<<f[maxx-1]<<endl; } return 0; }
6.Doing homework（hdu1074）
Problem Description
Input
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject's name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject's homework).
Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.
Output
Sample Input
Sample Output
Hint
In the second test case, both Computer->English->Math and Computer->Math->English leads to reduce 3 points, but the word "English" appears earlier than the word "Math", so we choose the first order. That is so-called alphabet order.f[i]=min(f[i-(1<<(j-1))+max(time[1-(1<<(j-1))]]+c[i]-d[i],0))
其中j为枚举的每门功课···而time[i]为完成i状态的功课所需的总时间···
这道题比较巧妙的一点是time会随着f的更新而更新···另外注意为了同一答案下保证按字典序小的答案输出··我们需要枚举j时从大到小枚举···
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> using namespace std; const int N=33000; int pre[N],f[N],n,dp[N],tim[N],fin[20],ded[N],T; char s[20][105]; inline void dfs(int u) { if(u==0) return; dfs(u-(1<<(pre[u]-1))); printf("%s ",s[pre[u]]); } int main() { //freopen("a.in","r",stdin); scanf("%d",&T); while(T--) { scanf("%d",&n);memset(f,0x3f3f3f3f,sizeof(f));f[0]=0; for(int i=1;i<=n;i++) scanf("%s%d%d",s[i],&ded[i],&fin[i]); for(int i=1;i<(1<<n);i++) { for(int j=n;j>=1;j--) { if(i&(1<<(j-1))) { int temp=i-(1<<(j-1)); int redu=((fin[j]+tim[temp]-ded[j])<0?0:fin[j]+tim[temp]-ded[j]); if(f[i]>f[temp]+redu) f[i]=f[temp]+redu,tim[i]=tim[temp]+fin[j],pre[i]=j; } } } cout<<f[(1<<n)-1]<<endl; dfs((1<<n)-1); } return 0; }