想当初，我听见大佬们谈起插头DP时，觉得插头DP是个神仙的东西。
某大佬：“考场见到插头DP，直接弃疗。”
现在，我终于懂了他们为什么这么说了。
因为——
插头DP很毒瘤！
为什么？
等等你就知道这是为什么了。
例题
hdu 1693 Eat the Trees
题目大意：给你一个地图，每个格子是空地或者障碍。现在要用若干个回路来覆盖这些空地，使得每个空地皆被一个回路覆盖。问方案数。
n,m<=11
How to solve it?
暴力？本人的暴力水平太弱了，对于这题，似乎连暴力都不好打。
So？咋做？
Of course,DP……
怎么划分阶段？
通常有逐行，逐列，逐格。你说的是什么鬼？
字面上的意思，逐行就是从上一行的状态转移到下一行，逐列类似。
逐格就是按照一定的顺序枚举每个格子（比如从上到下，从左到右），从上一个格子转移到下一个格子。
插头DP
插头是什么？
插头DP，最重要的当然是插头。
对于每一个格子，有上下左右四个插头，表示这个格子可以在这个方向与外面相连。
这题中，每个点的插头状况有下面七种。
其中，第0种情况是存在于障碍物的，剩下的6种存在于空地。
那么，我们在转移时，要接上轮廓线上边的插头，使其不会出现断头的情况。
轮廓线？就是你转移时候的一条线（没说一定是直线哈），这条线上面的每个格子都是你之前计算过的。
这幅图就是逐行转移的轮廓线。
做法
考虑逐行转移。
设表示枚举到第行，轮廓线上的下插头状态为的方案数。
怎么转移？
既然这是插头DP，那么转移的时候，就要接上上面的插头。
仔细地考虑一下，转移状态太多，不好枚举，时间复杂度显然无法接受。
那我们就试一下逐格转移。
先放个图。
设表示，枚举到行列，轮廓线上的插头状态为的方案数。
轮廓线上的插头显然是个下插头和1个右插头。
那么，转移？
既然要接上之前的插头，那么我们可以让之前的插头来接上它。
比如，1状态的格子的上方要有一个下插头，左边要有一个右插头。
2状态的格子上方要有一个下插头，左边不能有右插头。
那么我们枚举现在的状态，可以算出它从之前的那个状态推过来。
这个需要分类讨论……这就是插头DP毒瘤的原因。
还有一个比较毒瘤的是，最上面一行，最下面一行，以及最左边一列，需要特殊处理。
当然，如果你喜欢，最上面一行也不需特殊处理。
为什么要特殊处理？我觉得我不用说原因了。
代码
下面的代码，注释中例如no*yes，表示上面没有下插头，左边有一个右插头。
话说存状态的话，听说处理连通性的插头DP要按顺序存，这里为图方便，就将右插头存到了最后。
/*Situation:
1:up left
2:down up
3:down left
4:down right
5:right left
6:right up
*/
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
int n,m;
int mat[11][11];
long long f[11][11][4096];
int main()
{
// freopen("in.txt","r",stdin);
// freopen("test.txt","w",stdout);
int T;
scanf("%d",&T);
for (int TT=1;TT<=T;++TT)
{
scanf("%d%d",&n,&m);
for (int i=0;i<n;++i)
for (int j=0;j<m;++j)
scanf("%d",&mat[i][j]);
memset(f,0,sizeof f);
if (mat[0][0])
f[0][0][1<<0|1<<m]=1;//4
else
f[0][0][0]=1;//Space
for (int j=1;j<m;++j)
if (mat[0][j])
{
for (int s_=0;s_<1<<j+1;++s_)
if (s_>>j&1)
{
int s=s_|1<<m;
f[0][j][s]+=f[0][j-1][s_^1<<j];//no*no->4
s=s_;
f[0][j][s]+=f[0][j-1][s_^1<<j|1<<m];//no*yes->3
}
else
{
int s=s_|1<<m;
f[0][j][s]+=f[0][j-1][s_|1<<m];//no*yes->5
}
}
else
{
for (int s=0;s<1<<j;++s)
f[0][j][s]+=f[0][j-1][s];
}
for (int i=1;i<n-1;++i)
{
if (mat[i][0])
{
for (int s_=0;s_<(1<<m);++s_)
if (s_&1)
{
int s=s_|1<<m;
f[i][0][s]+=f[i-1][m-1][s_^1];//no*no->4
s=s_;
f[i][0][s]+=f[i-1][m-1][s_];//yes*no->2
}
else
{
int s=s_|1<<m;
f[i][0][s]+=f[i-1][m-1][s_|1];//yes*no->6
}
}
else
{
for (int s=0;s<(1<<m);s+=2)
f[i][0][s]+=f[i-1][m-1][s];//no*no->Space
}
for (int j=1;j<m;++j)
if (mat[i][j])
{
for (int s_=0;s_<1<<m;++s_)
if (s_>>j&1)
{
int s=s_|1<<m;
f[i][j][s]+=f[i][j-1][s_^1<<j];//no*no->4
s=s_;
f[i][j][s]+=f[i][j-1][s_]+f[i][j-1][s_^1<<j|1<<m];//yes*no->2 no*yes->3
}
else
{
int s=s_|1<<m;
f[i][j][s]+=f[i][j-1][s_|1<<m]+f[i][j-1][s_|1<<j];//no*yes->5 yes*no->6
s=s_;
f[i][j][s]+=f[i][j-1][s_|1<<j|1<<m];//yes*yes->1
}
}
else
{
for (int s=0;s<1<<m;++s)
if (!(s>>j&1))
f[i][j][s]+=f[i][j-1][s];//no*no->Space
}
}
if (mat[n-1][0])
{
for (int s_=0;s_<(1<<m);++s_)
if (!(s_&1))
{
int s=s_|1<<m;
f[n-1][0][s]+=f[n-1-1][m-1][s_|1];//yes*no->6
}
}
else
{
for (int s=0;s<(1<<m);s+=2)
f[n-1][0][s]+=f[n-1-1][m-1][s];//no*no->Space
}
for (int j=1;j<m;++j)
if (mat[n-1][j])
{
for (int s_=0;s_<1<<m;++s_)
if (!(s_>>j&1))
{
int s=s_|1<<m;
f[n-1][j][s]+=f[n-1][j-1][s_|1<<m]+f[n-1][j-1][s_|1<<j];//no*yes->5 yes*no->6
s=s_;
f[n-1][j][s]+=f[n-1][j-1][s_|1<<j|1<<m];//yes*yes->1
}
}
else
{
for (int s=0;s<1<<m;++s)
if (!(s>>j&1))
f[n-1][j][s]+=f[n-1][j-1][s];//no*no->Space
}
long long ans=f[n-1][m-1][0];
printf("Case %d: There are %lld ways to eat the trees.
",TT,ans);
}
return 0;
}总结
插头DP的关键是，转移的时候要连上之前的插头，保证不要断掉。
打插头DP需要非常严谨，打错了就不妙了，还不好调。
某大佬说，这不是标准的插头DP，因为标准的插头DP还要维护连通性，好像是用什么括号序。
我才懒得管这么多，感性理解一下，插头DP就是有插头的DP吧……不过那些维护连通性的题，若有机会，我定会光顾一下。
这题作为例题，还是很好的。