第一次做状态压缩DP，是因为按照DP清单里面碰到了状态不确定的DP，我当时只能用回溯做，但是时间卡得想死啊，后来又连续碰到几个题目都需要用状态压缩，所以好好学了一下，说到这里，必须要检讨一下昨天的自己，其实这道题目本应该昨天完成的，自己磨磨蹭蹭昨天非常地心不在焉，弄得昨天完全没完成训练任务。加上这个位运算这里确实有点难懂，我之前很少接触位运算，但是用状态压缩的时候位运算贯穿整个代码，所以理解起来比较难
还好找到了一个讲解非常详细的博文，这才理解了 http://www.2cto.com/kf/201208/146894.html 这个博文写的非常好
还有这个题目跑了900+MS，在学校的VJ上有100+MS过的，我看了下，先用的一个dfs在预处理，我没怎么看懂为什么是么是这样搞。。。。再说吧
注意两点：1。结果可能非常大，因此要用long long
2.行如果小于列的话，交换一下，能大大缩小时间复杂度，因为m的递增导致循环里面是成指数的增长
继续加油
|
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#include <iostream>#include <cstdio>#include <cstring>#define N (1<<11)+20#define ll long longusing
namespace
std;
ll dp[12][N];int
n,m;
bool
testfirst(int
d)
{ int
i=0;
while
(i<m)
{
if
(d & (1<<i))
{
if
(i==m-1 || (d & (1<<(i+1)))==0)
{
return
false;
}
i+=2;
}
else
i++;
}
return
true;
}bool
test(int
a,int
b)
{ int
i=0;
while
(i<m)
{
if
((a & (1<<i))==0)
{
if
((b & (1<<i))==0)
return
false;
i++;
}
else
{
if
((b & (1<<i))==0)
i++;
else
{
if
(i==m-1 || !(a& (1<<(i+1))) || !(b & (1<<(i+1))))
{
return
false;
}
i+=2;
}
}
}
return
true;
}int
main()
{ int
i,j,k;
while
(scanf("%d%d",&n,&m))
{
if
(n+m==0) break;
if
(n*m%2!=0)
{
puts("0");
continue;
}
if
(n<m)
{
int
temp=n;
n=m;
m=temp;
}
memset(dp,0,sizeof
dp);
for
(i=0; i<N; i++)
{
if
(testfirst(i))
{
dp[0][i]=1;
}
}
for
(i=1; i<n; i++)
{
for
(j=0; j<(1<<m); j++)
{
for
(k=0; k<(1<<m); k++)
{
if
(test(j,k))
{
dp[i][j]+=dp[i-1][k];
}
}
}
}
printf("%lld\n",dp[n-1][(1<<m)-1]);
}
return
0;
} |