pku_3254_Corn Fields
【题目概述】告诉平面上一些点，从中选择部分点出来，要求不能选择相邻的点，求所有的方案数。
【题目分析】学过gohst—wei的代码风格之后，第一道小练兵。花的时间虽然长了点，但是，感觉还不错。
1. 首先还是分析采取由上而下，逐行分析的策略。
2. 我们发现，影响当前行的状态的只有上一行，即上一行和下一行的要满足相邻不相等原则。
3. 设 表示前i行的方案数，且第i行的状态为s.
转移方程：
（其中，t为上一行的某个与当前行不相冲突的状态）
4. 时间复杂度为 显然这样的复杂度为不满足条件的。因此需要优化
5. 我们发现，题目中有一个限制的条件是没用到的。就是同一行也不满足相邻不可取的。由此，我们可以实现预处理，剔除掉多余的状态，这样，最后的每行合法的状态，最多只有367个。
【题目代码】下面是AC的代码。
//Name: pku_3254_Corn Fields
#include <iostream>
using namespace std;
const int maxs = 1<<12;
const int mod = 100000000;
int map[13][13], n, m;
int stk[maxs], sn;
int dp[2][maxs];
inline bool one(int i, int j) { return (i&(~(1<<j))) != i;}
bool check(int i, int j) {
if (j > 0 && one(i, j-1)) return 0;
if (j < m-1 && one(i, j+1)) return 0;
return 1;
}
void Proced(int km, int m) {
sn = 0; int i, j;
for (i = 0,j; i < km; i++) {
for (j = 0; j < m; j++)
if(one(i, j) && !check(i,j)) break;
if (j == m) stk[sn++] = i;
}
// for (i = 0; i < sn; i++) printf("stk[%d] = %d\n", i, stk[i]);
}
void SCDP() {
int i, j, s1, s2, k1, k2, e1 = 0, e2 = 1;
for (j = 0; j < sn; j++) dp[0][stk[j]] = 0;
dp[0][0] = 1;
for (i = 1; i <= n; i++) {
for (j = 0; j < sn; j++) dp[e2][stk[j]] = 0;
for (k1 = 0; k1 < sn; k1++) {
for (k2 = 0; k2 < sn; k2++) {
s1 = stk[k1]; s2 = stk[k2];
if(s1 & s2)continue;
for(j = 0; j < m; j++)
if (!map[i][j] && one(s2, j)) break;
if (j == m) {
dp[e2][s2] = (dp[e2][s2]+dp[e1][s1])%mod;
}
}
}
e1 ^= 1; e2 ^= 1;
}
int ans = 0;
for (k1 = 0; k1 < sn; k1++)
ans = (ans + dp[e1][stk[k1]])%mod;
printf("%d\n", ans);
}
int main() {
freopen("in.in", "r", stdin);
scanf("%d %d", &n, &m);
Proced(1<<m, m);
for(int i = 1; i <= n; i++)
for (int j = 0; j < m; j++)
scanf("%d", map[i]+j);
SCDP();
return 0;
}