这种动归有很多名字，插头DP是最常见的
还有基于连通性的动态规划
轮廓线动态规划等等
超小数据范围，网格图，连通性
可能算是状态压缩DP的一种变式
以前我了解的状压DP用于NP难题的小数据范围求解
这里说一下哈密顿回路的概念：
哈密顿回路： 1、指一个对图的每个顶点都只穿越一次的回路。也可以 定义为n+1个相邻顶点v0, v1, … ,vn, v0的一个序列，其中序列的第一个顶点和最后一个顶点是相同的，而其他n-1个顶点是互不相同的。 2、当这个图是加权图时，求该图的最短哈密顿回路，就是传说中的旅行商问题（TSP）。
然后是一道插头DP的入门题
一个网格图中有若干障碍格子，求其他格子的哈密尔顿回路总数
1 #include2 using namespace std; 3 typedef long long LL; 4 const int LIM=300005,Has=299989; 5 int n,m,e1,e2,las,now,tt;LL ans; 6 int mp[15][15],bin[15],tot[2];LL js[2][LIM]; 7 int h[300005],a[2][LIM],ne[LIM]; 8 //tot:状态总数,js:该状态的方案总数,a:各种状态 9 void ins(int zt,LL num) { //卓越的哈希技术10 int tmp=zt%Has+1;11 for(int i=h[tmp];i;i=ne[i])12 if(a[now][i]==zt) {js[now][i]+=num;return;}13 ne[++tot[now]]=h[tmp],h[tmp]=tot[now];14 a[now][tot[now]]=zt,js[now][tot[now]]=num;15 }16 void work() {17 tot[now]=1,js[now][1]=1,a[now][1]=0;18 for(int i=1;i<=n;++i) {19 for(int j=1;j<=tot[now];++j) a[now][j]<<=2;//切换行了20 for(int j=1;j<=m;++j) {21 las=now,now^=1;22 memset(h,0,sizeof(h)),tot[now]=0;23 for(int k=1;k<=tot[las];++k) {24 int zt=a[las][k],b1=(zt>>(j*2-2))%4,b2=(zt>>(j*2))%4;//提取关键格子上的两段轮廓线状态25 LL num=js[las][k];26 if(!mp[i][j]) { if(!b1&&!b2) ins(zt,num);}27 else if(!b1&&!b2) 28 { if(mp[i+1][j]&&mp[i][j+1]) ins(zt+bin[j-1]+2*bin[j],num);}29 else if(!b1&&b2) {30 if(mp[i][j+1]) ins(zt,num);31 if(mp[i+1][j]) ins(zt-bin[j]*b2+bin[j-1]*b2,num);32 }33 else if(b1&&!b2) {34 if(mp[i][j+1]) ins(zt-bin[j-1]*b1+bin[j]*b1,num);35 if(mp[i+1][j]) ins(zt,num);36 }37 else if(b1==1&&b2==1) {38 int kl=1;39 for(int t=j+1;t<=m;++t) {40 if((zt>>(t*2))%4==1) ++kl;41 if((zt>>(t*2))%4==2) --kl;42 if(!kl) {ins(zt-bin[j]-bin[j-1]-bin[t],num);break;}43 }44 }45 else if(b1==2&&b2==2) {46 int kl=1;47 for(int t=j-2;t>=0;--t) {48 if((zt>>(t*2))%4==1) --kl;49 if((zt>>(t*2))%4==2) ++kl;50 if(!kl) {ins(zt+bin[t]-2*bin[j]-2*bin[j-1],num);break;}51 }52 }53 else if(b1==2&&b2==1) ins(zt-2*bin[j-1]-bin[j],num);54 else if(i==e1&&j==e2) ans+=num;55 }56 }57 }58 }59 int main()60 {61 scanf("%d%d",&n,&m);62 for(int i=1;i<=n;++i)63 for(int j=1;j<=m;++j) {64 char ch=getchar();65 while(ch!='*'&&ch!='.') ch=getchar();66 if(ch=='.') mp[i][j]=1,e1=i,e2=j;67 }68 bin[0]=1;for(int i=1;i<=12;++i) bin[i]=bin[i-1]<<2;69 work(),printf("%lld\n",ans);70 return 0;71 }
然后是HDU1693
给一个n*m的地图，有些格子是不可到达的，要把所有可到达的格子的树都吃完，并且要走回路，求方案数
允许有多个回路，找一条或多条回路，吃完所有的树
1 #include2 using namespace std; 3 typedef long long LL; 4 int n,m,T,kas,bin[15],mp[15][15];LL f[12][12][(1<<12)]; 5 int main() 6 { 7 scanf("%d",&T); 8 bin[0]=1;for(int i=1;i<=12;++i) bin[i]=bin[i-1]<<1; 9 while(T--) {10 scanf("%d%d",&n,&m);11 for(int i=1;i<=n;++i)12 for(int j=1;j<=m;++j) scanf("%d",&mp[i][j]);13 memset(f,0,sizeof(f));14 f[0][m][0]=1;int lim=bin[m+1]-1;15 for(int i=1;i<=n;++i) {16 for(int zt=0;zt<=lim;++zt) f[i][0][zt<<1]=f[i-1][m][zt];17 for(int j=1;j<=m;++j)18 for(int zt=0;zt<=lim;++zt) {19 int b1=zt&bin[j-1],b2=zt&bin[j];LL num=f[i][j-1][zt];20 if(!mp[i][j]) { if(!b1&&!b2) f[i][j][zt]+=num;}21 else if(!b1&&!b2) 22 { if(mp[i][j+1]&&mp[i+1][j])f[i][j][zt+bin[j-1]+bin[j]]+=num;}23 else if(!b1&&b2) {24 if(mp[i][j+1]) f[i][j][zt]+=num;25 if(mp[i+1][j]) f[i][j][zt-bin[j]+bin[j-1]]+=num;26 }27 else if(b1&&!b2) {28 if(mp[i][j+1]) f[i][j][zt-bin[j-1]+bin[j]]+=num;29 if(mp[i+1][j]) f[i][j][zt]+=num;30 }31 else f[i][j][zt-bin[j-1]-bin[j]]+=num;32 }33 }34 printf("Case %d: There are %lld ways to eat the trees.\n",++kas,f[n][m][0]);35 }36 return 0;37 }