pku_3254_Corn Fields
【題目概述】告訴平面上一些點(diǎn)，從中選擇部分點(diǎn)出來，要求不能選擇相鄰的點(diǎn)，求所有的方案數(shù)。
【題目分析】學(xué)過gohst—wei的代碼風(fēng)格之后，第一道小練兵。花的時(shí)間雖然長了點(diǎn)，但是，感覺還不錯。
1. 首先還是分析采取由上而下，逐行分析的策略。
2. 我們發(fā)現(xiàn)，影響當(dāng)前行的狀態(tài)的只有上一行，即上一行和下一行的要滿足相鄰不相等原則。
3. 設(shè) 表示前i行的方案數(shù)，且第i行的狀態(tài)為s.
轉(zhuǎn)移方程：
（其中，t為上一行的某個與當(dāng)前行不相沖突的狀態(tài)）
4. 時(shí)間復(fù)雜度為 顯然這樣的復(fù)雜度為不滿足條件的。因此需要優(yōu)化
5. 我們發(fā)現(xiàn)，題目中有一個限制的條件是沒用到的。就是同一行也不滿足相鄰不可取的。由此，我們可以實(shí)現(xiàn)預(yù)處理，剔除掉多余的狀態(tài)，這樣，最后的每行合法的狀態(tài)，最多只有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;
}