不总结的话, 同一个地方会 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;
}