P1879 [USACO06NOV]Corn Fields G

对于每一行，预处理所有的合法方案。一个判断相邻两行是否同时选择的技巧是，判断他们的 & 值是否为 $0$ ，当且仅当有一位同时为 $1$ 时，得数在该位为 $1$ ，得数大于 $0$ 。

查看代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 5e3 + 10, mod = 1e8;
bool avai[15][15];
int m, n, cnt[15], state[15][N], f[15][N];
int main ()
{
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> avai[i][j];
    for (int k = 0; k < m; k++)
        for (int i = 0; i < 1 << n; i++)
        {
            bool flag = true;
            for (int j = 0; j < n; j++)
                if (((i >> j & 1) & (i >> j + 1 & 1)) || (!avai[k][j] && i >> j & 1))
                {
                    flag = false;
                    break;
                }
            if (flag)
                state[k][++cnt[k]] = i;
        }
    for (int i = 1; i <= cnt[0]; i++)
        f[0][i] = 1;
    for (int i = 1; i < m; i++)
        for (int x = 1; x <= cnt[i]; x++)
            for (int y = 1; y <= cnt[i - 1]; y++)
                if ((state[i][x] & state[i - 1][y]) == 0)
                    f[i][x] = (f[i][x] + f[i - 1][y]) % mod;
    int res = 0;
    for (int i = 0; i < 1 << n; i++)
        res    = (res + f[m - 1][i]) % mod;
    cout << res;
    return 0;
}