这个题目去年就过了，用得是状态压缩dp，不过没用dfs预处理，当时做得不是很明白，还是参考网上的一个代码做的。
现在重新做了一下这个题目，请教了icecream，学会了一个很简练的做法，而且比较好理解还好写。
首先还是状态的表示，用0表示没有放木块，用1表示放了木块。此外，对于一个横放的木块，对应的两位都用1表示；对于一个竖放的木块，第一行用1表示，第二行用0表示。这只是一种设状态的方式，当然还有别的设法，但是这种方法在接下来就会发现优点。
状态表示完就要处理转移了，如何判断一个转移是否合法比较难办，用一个dfs却可以简洁的解决这个问题。
对于上一行到下一行的转移，规定上一行一定填满，这样有三种方式：
dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
第一种上面是1，那么下面一定是0，表示是一个竖放的木块。
第二种上面是0，就是说这个位置一定是一个竖放木块的下半截，那么下一行肯定是要另起一行了，放一个竖放或者横放的木块都必须是1。
第三种相当于上下两行各放一个横木块。
实现的时候我用了一个vector记录每个状态所有可行的转移，这样在dp的时候可以加快一些效率。
还有一个问题需要考虑，那就是初值和最终的结果。如果寻找合法状态，依然比较麻烦，假设共有n行，可以分别在这n行上下新加两行。下面一行都是1，由于第n行肯定要填满，这样新加的全1的行就相当于顶住了第n行使其没有凸出（有凸出那么第n+1行有0），而通过第n行到第n+1行转移保留了所有合法状态；同理最上面加的那行保证第一行没有凸出。最后第n+1行对应全1的状态就是最终的结果了。通过新加行巧妙地解决了初值和终值。
实现的时候也需要注意一下，在TSP问题中，外层循环是状态，内层是点，之所以这样写因为在枚举点的时候，可能会从比当前编号大的点转移，但是由于无论怎样转移过来的状态肯定比当前状态小（去掉了1），所以先从小到大枚举状态就保证转移过来的状态一定是算过的。而这个题目里面正好反过来，因为状态可能从比当前状态大的状态转移过来，而行数肯定是从编号小的行转移，因此先枚举行就能保证转移过来的状态一定是更新过的。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 11;
vector<int> g[1<<N];
long long dp[N+2][1<<N];
void dfs(int col, int s1, int s2, int n)
{
if (col >= n)
{
if (s1 < (1 << n) && s2 < (1 << n))
g[s2].push_back(s1);
return;
}
dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
}
long long calc(int m, int n)
{
if (m < n) swap(m, n);
dfs(0, 0, 0, n);
int state = 1 << n;
dp[0][0] = 1;
for (int i = 1; i <= m + 1; i++)
for (int s = 0; s < state; s++)
for (int j = 0; j < g[s].size(); j++)
dp[i][s] += dp[i-1][g[s][j]];
return dp[m+1][state-1];
}
int main()
{
int m, n;
while (scanf("%d %d", &m, &n) == 2)
{
if (m == 0 && n == 0)
break;
for (int i = 0; i < (1 << N); i++)
g[i].clear();
memset(dp, 0, sizeof(dp));
printf("%I64d\n", calc(m, n));
}
return 0;
}