poj 3254 Corn Fields （状压dp）（棋盘dp）

状压dp入门题

因为当前行的状态只和上一行有关

所以可以一行一行来做

因为m <= 12所以可以用二进制来表示放了或者没有放

0表示没放，1表示放

f[i][state]表示第i行状态为state的方案数

f[i][state] = sum(f[i-1][state'])

枚举行，然后枚举这一行和上一行的状态

最后把最后一行所有状态的和加起来就行了

状态是这么定义，但是实际操作略有不同

因为state的状态有很多被剔除，所以我们可以只存

state数组的下标来省空间

也就是说f[i][j]表示第i行状态为state[j]的方案数

这一点貌似其他博客都没有提到。

还有几个点要注意

（1）怎么表示左右没有相邻？

这里有个骚操作 x & (x << 1)

如果这个值为真，就表示有1相邻。

这是显而易见的，不懂得拿笔画一下就知道了

可以一开始就把不可行的状态剔除，非常省时间

（2）怎么表示上下没有相邻

两行的状态取&，值为真就有相邻

（3）题目给的限制条件怎么用

题目中说0就是不可以放

那么如果是0就设为1，然后和当前状态取&

如果值为真就说明有重合，就不行

（4）最后，一个小细节

我一开始是写如果到第n - 1行（我从0开始），就更新答案。

然后是WA。

如果是单独写一个循环来更新，就AC

想了想，发现如果只有一行的话，第一种写法答案是不会被更新的。

因为如果只有一行循环根本不会进行！！！

我第一次遇到这样的坑，以后要注意

#include<cstdio>

#include<vector>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 20;

const int MAXM = 600;

const int MOD = 1e8;

int f[MAXN][MAXM], map[MAXN], n, m;

vector<int> state;

inline bool judge(int x) { return !(x & (x << 1)); }

inline bool fit(int x, int i) { return !(x & map[i]); }

void init()

{

	REP(i, 0, 1 << m)

		if(judge(i))

			state.push_back(i);

}

int main()

{

	while(~scanf("%d%d", &n, &m))

	{

		memset(f, 0, sizeof(f));

		state.clear(); init();

		REP(i, 0, n)

		{

			map[i] = 0;

			REP(j, 0, m)

			{

				int x; scanf("%d", &x);

				if(x == 0) map[i] |= (1 << (m - j - 1));

			}

		}

		REP(i, 0, state.size())

			if(fit(state[i], 0))

				f[0][i] = 1;

		int ans = 0;

		REP(i, 1, n)

			REP(j, 0, state.size())

			{

				if(!fit(state[j], i)) continue;

				REP(k, 0, state.size())

				{

					if(!fit(state[k], i-1)) continue;

					if(state[j] & state[k]) continue;

					f[i][j] = (f[i][j] + f[i-1][k]) % MOD;

				}

			}

		_for(i, 0, state.size()) ans = (ans + f[n-1][i]) % MOD;

		printf("%d\n", ans);

	}

	return 0;

}