POJ 1321 棋盘问题(状态压缩DP)

不总结的话, 同一个地方会 WA 到死

思路:

状态压缩 DP.

1. s 表示压缩状态, 若第 i 列放了棋子, 那么该列置 1, 否则该列置 0. 假如 s = 3(0x011) 那么表示棋盘的第 2, 3 列已经放了棋子

2. dp[i][s] 表示前 i 行, 状态为 s 的摆放方案数

　 dp[i][s] = dp[i-1][s] 假如第 i 行不放棋子

　 dp[i][s] = dp[i-1][oldState] 假如第 i 行放棋子

3. 棋盘的最大长宽为 8, 所以 s 的状态最多有 1<<8 个, 用 int 足以

4. 此题能用状态压缩的根源在于每一列只能摆放一个棋子

总结:

1. dp 框架问题. 最外一层循环, 遍历的是行数, 这个比较明显, 而第二层循环遍历的是状态 s, 根据是 dp 的定义 dp[i][s], 至于 j, 只能放在第三层

2. 空间优化. dp[i][s] 可以优化到 dp[s], 代价是第二层循环 s 必须从大到小遍历, 这样才能保证 push 更新 --- 考虑状态转移方程

　　dp[i][s] = dp[i-1][s] , dp[i-1][oldS], 等号右边的 s, oldS 编号都是第 i-1 层的, 假如对 s 正向遍历, 那么 s , oldS 对应的就是第 i 层的了

3. 错误点. i 的起始是 (1<<N)-1, 这地方第一次做这题错了, 写成 1<<8

4. 错误点. 移位的优先级较低, 需要加括号 (1<<N)-1

5. bitset 操作

for(int i = 0; i < 1<<n; i ++) {

		bitset<10> getOne(i);

		if( getOne.count() == c)

			res += record[i];

}

6. record[0] = 1 比较精髓, 空间优化后的一个好处是初始化比较简单

7. 位操作, &, |

代码:

#include <bitset>

#include <iostream>

using namespace std;

const int MAXN = 10;

char grid[MAXN][MAXN];

int record[1<<8];

int N, K;

int mainFunction() {

	memset(record, 0, sizeof(record));

	record[0] = 1; // very talent

	for(int i = 0; i < N; i ++) {

		for(int s = (1<<N)-1; s >= 0; s--) {

			for(int j = 0; j < N; j++) {

				if(grid[i][j]=='#' &&((1<<j)&s)==0) {

					record[s|(1<<j)] += record[s];

				}

			}

		}

	}

	int sum = 0;

	for(int s = (1<<N)-1; s > 0; s --) {

		bitset<10> temp(s);

		if(temp.count() == K)

			sum += record[s];

	}

	return sum;

}

int main() {

	freopen("E:\\Copy\\ACM\\poj\\2_1321\\in.txt", "r", stdin);

	while(cin >> N >> K && N != -1) {

		for(int i = 0; i < N; i ++) {

			for(int j = 0; j < N; j ++) {

				cin >> grid[i][j];

			}

		}

		cout << mainFunction() << endl;

	}

	return 0;

}

巴特西

POJ 1321 棋盘问题(状态压缩DP)

最新文章

热门文章