经典的状压DP题，解法很多
这里讲下状压轮廓线的做法
s 从大到小保存
若，必须要竖放一个
否则可以横放也可以不放1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
const int N=18;
int n,m;
LL dp[2][1<<N];
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
int main()
{
while (n=read(),m=read())
{
if (n<m) swap(n,m);
for(int s=0;s<(1<<m);s++) dp[0][s]=0;
dp[0][(1<<m)-1]=1;
for(int i=1,now=1;i<=n;i++)
for(int j=1;j<=m;j++,now^=1)
{
for(int s=0;s<(1<<m);s++) dp[now][s]=0;
for(int s=0;s<(1<<m);s++)
if (!(s>>(m-1))&1)
dp[now][(s<<1)|1]+=dp[now^1][s];
else
{
dp[now][(s<<1)&((1<<m)-1)]+=dp[now^1][s];
if (j!=1&&!(s&1)) dp[now][((s<<1)|3)&((1<<m)-1)]+=dp[now^1][s];
}
}
printf("%lld\n",dp[(n*m)&1][(1<<m)-1]);
}
return 0;
}