题解 P1879 【[USACO06NOV]玉米田Corn Fields】

· · 题解

分析

数据大小已经很明显的提示，这题是状压DP啊！

读入以后，我们用F[i]来表示第i行上的草地情况，这里F数组里的是二进制数。MAXSTATE是2n，也就是这道题的最大状态（n列都是1）。

然后我们在0~MAXSTATE-1这些状态里找到合法状态，也就是不能两头牛的草地是相邻的。判断方法就是把这个二进制数左移一位and，然后右移一位and。如果这个状态是合法的，那么都应该返回0。

然后就开始动规，从第一行开始，在每行里找所有状态，如果这个状态是合法的，且不会在贫瘠的草地上（和(j & F[i]) == j说明没有草地种在贫瘠的地方），那么接下来开始找上一行的合法情况（上下两行之间没有相邻的草地），把上一行的情况数加到f[i][j]里。

最后把最下面一行的每一列的情况书统统加起来，就是答案啦~

程序

#include <bits/stdc++.h>
using namespace std;
const int M = 1e9;
int m, n, f[13][4096], F[13], field[13][13];
// max state: (11111111111)2 = (4095)10
bool state[4096];
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> field[i][j];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            F[i] = (F[i] << 1) + field[i][j];
    // F[i]: state on line i
    int MAXSTATE = 1 << n;
    for (int i = 0; i < MAXSTATE; i++)
        state[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);
    f[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < MAXSTATE; j++)
            if (state[j] && ((j & F[i]) == j))
                for (int k = 0; k < MAXSTATE; k++)
                    if ((k & j) == 0)
                        f[i][j] = (f[i][j] + f[i-1][k]) % M;
    int ans = 0;
    for (int i = 0; i < MAXSTATE; i++)
        ans += f[m][i], ans %= M;
    cout << ans << endl;
    getchar();
    getchar();
    return 0;
}