状态压缩DP：这类问题有TSP、插头dp ，轮廓线DP等。
参考大佬的总结：http://blog.csdn.net/renl1000/article/details/53126502
基本状压：
poj 3254：
分析：经典状态压缩
以行为阶段递推.每一行的状态用01状态表示。1代表放，0代表不放。
预处理求出满足不相连的01状态。大大节省时间。
#include <iostream> #include<stdio.h> #include<string.h> #include<algorithm> const int maxn = 15; const int mod = 100000000; using namespace std; int n,m; int d[maxn][(1<<maxn)]; int st[(1<<maxn)],g[maxn]; int ok(int S) { return (S&(S<<1)); } int fuck(int x,int y)// 判断x y 是否有相连的1. { return x&y; } void solve() { memset(d,0,sizeof(d)); int tot = 0; for(int S=0; S<(1<<m); S++) { if(!ok(S)) st[++tot] = S;// 一行中1不相连的状态。 } for(int i=1; i<=tot; i++) { if(!fuck(st[i],g[1])) d[1][i] = 1;//初始化 第一行 。 } for(int i=2; i<=n; i++) { for(int j=1; j<=tot; j++) { if(fuck(st[j],g[i])) continue;// 如果此状态为不符合状态则不要 for(int k=1; k<=tot; k++) { if(fuck(st[k],g[i-1])) continue;// 如果此状态为不符合状态则不要 if(!fuck(st[k],st[j])) d[i][j]+=d[i-1][k];// 与上一行的1不相连。 } } } int ans = 0; for(int i=1; i<=tot; i++) ans = (ans + d[n][i])%mod; printf("%d\n",ans); } int main() { int x; while(~scanf("%d %d",&n,&m)) { memset(g,0,sizeof(g)); for(int i=1; i<=n; i++) { for(int j=0; j<m; j++) { scanf("%d",&x); if(!x) g[i]|=(1<<j); } } solve(); } return 0; } poj 1185：分析：
与上题类似，也是压缩每一行的放与不放的状态。
就是 每一行与前两行有关。所以状态转换方程为：设d[i][j][k] 第i行状态为j,i-1行为k的状态。 则： d[i][j][k] = d[i-1][k][t].
#include <iostream> #include<stdio.h> #include<string.h> #include<algorithm> const int maxn = 100; const int inf = 1e9; using namespace std; int n,m; int g[maxn+5]; int st[(1<<11)],d[maxn+5][65][65]; bool ok(int S) { if((S&(S<<1))||(S&(S<<2))) return false; return true; } int bit(int S) { int cnt = 0; for(int i=0; i<=10; i++) if(S&(1<<i)) cnt++; return cnt; } bool fuck(int x,int y) { return x&y; } void solve() { int tot = 0,ans=0; memset(d,0,sizeof(d)); for(int S=0; S<(1<<m); S++) { if(ok(S)) st[++tot] = S; } for(int i=1; i<=tot; i++) { if(!fuck(st[i],g[1])) d[1][i][1] = bit(st[i]),ans = max(ans,d[1][i][1]); } for(int i=2; i<=n; i++) { for(int j=1; j<=tot; j++) { if(g[i]&st[j]) continue; for(int k=1; k<=tot; k++) { if(g[i-1]&st[k]) continue; if(st[k]&st[j]) continue; for(int t=1; t<=tot; t++) { if(g[i-2]&st[t]) continue; if((st[k]&st[t])||(st[j]&st[t])) continue; d[i][j][k] = max(d[i][j][k],d[i-1][k][t] + bit(st[j])); ans = max(ans,d[i][j][k]); } } } } printf("%d\n",ans); } int main() { char S[15]; while(~scanf("%d %d",&n,&m)) { for(int i=1; i<=n; i++) { scanf("%s",S); g[i] = 0; for(int j=0; j<m; j++) { if(S[j]=='H') g[i]|=(1<<j); } } solve(); } return 0; }轮廓线动态规划与插头DP：
poj 2411：（挑战程序设计）
/* 轮廓状态dp。有点难推。发现推得方向不同状态装换难易不同。 */ #include <iostream> #include<string.h> #include<algorithm> #include<stdio.h> const int maxn = 12; typedef long long LL; using namespace std; int h,w; LL d[2][(1<<maxn)+5]; void solve() { memset(d,0,sizeof(d)); int crt = 0, nex = 1; d[crt][0]=1; for(int i=h-1; i>=0; i--) { for(int j=w-1; j>=0; j--) { for(int S=0; S<(1<<w); S++) { if(S&(1<<j)) { d[nex][S] = d[crt][S^(1<<j)]; } else { LL ret = 0; if(j+1<w&&!(S&(1<<(j+1)))) ret+=d[crt][S^(1<<(j+1))]; if(i+1<h) ret+=d[crt][S|(1<<j)]; d[nex][S] = ret; } } swap(nex,crt); } } printf("%I64d\n",d[crt][0]); } int main() { while(scanf("%d %d",&h,&w)&&(h+w)) { solve(); } return 0; }