Description

P1879 [USACO06NOV]Corn Fields G

Solution

状压\(dp\) 基础题。

定义状态： \(f[i][j]\) 表示到第 \(i\) 行，且第 \(i\) 行种植状态为 \(j\) 的总方案数。

我们先把每一行的状态记录下来。

枚举每一行，由于当前行的值只能由上一行转移过来，所以枚举当前行状态，再枚举上一行状态。

判断能否进行转移，然后转移即可。

先说判断：设当前行状态为 \(s1\)，上一行状态为 \(s2\)，那么

• \(s1\) & \((s1 >> 1)\) == 0，\(s2\) 同理（相邻两位没有都种植的）

• \(s1\) & \(s2\) == 0，（上下两行对应位没有都种植的）。

• \((s1 | sta[i]) == sta[i]\)，\(s2\) 同理，注意是和 \(sta[i-1]\) 判断。（当前枚举的种植状态是符合当土地条件的）

转移方程： \(f[i][s1] = (f[i][s1] + f[i - 1][s2]) \ \% \ mod\)

这个就很简单了吧，当然要在上述条件都符合的情况下才能转移。

注意：优先级是个很迷的东西，上面我写的判断的式子优先级是有问题的，主要是为了美观，自己写的时候括号能加就加。

Code

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e8;
int n, m;
int sta[13], f[13][1 << 13];

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1, x; j <= m; j++){
            scanf("%d", &x);
            sta[i] = sta[i] << 1 | x;
        }
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int s1 = 0; s1 < (1 << m); s1++)
            for(int s2 = 0; s2 < (1 << m); s2++)
                if(!(s1 & (s1 >> 1)) && !(s2 & (s2 >> 1)) && !(s1 & s2) && (s1 | sta[i]) == sta[i] && (s2 | sta[i - 1]) == sta[i - 1])
                    f[i][s1] = (f[i][s1] + f[i - 1][s2]) % mod;
    int ans = 0;
    for(int i = 0; i < (1 << m); i++)
        ans = (ans + f[n][i]) % mod;
    printf("%d\n", ans);
    return 0;
}

End