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

其实这道题可以套用插头DP的模板。(虽然有点大材小用)

我们考虑定义状态 $f(i,j,k)$ 表示当前正在安排第i行第j列,其中k是一个二进制数,它表示

$(i,1)\to(i,j-1)$ $(i-1)(j)\to(i-1,m)$

这几个格子有没有被种上草。

如果$(i-1,j) or(i,j-1)$ 有草,我们就只能转移到不种草,否则可种可不种。

这样的话时间复杂度是 $O(n^22^n)$ 的。

我的代码写复杂了。

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int MOD = 100000000;
int n, m;
long long ans;
int ch[20], c[20][20];
long long f[15][15][1 << 14];

void inc(long long &a, long long b)
{
    a = (a % MOD + b % MOD) % MOD;
}

long long encode()
{
    long long ret = 0;
    for (int i = m; i > -1; --i)
    {
        ret <<= 1;
        ret |= ch[i];
    }
    return ret;
}

void decode(long long v)
{
    for (int i = 0; i < m + 1; ++i)
    {
        ch[i] = v & 1;
        v >>= 1;
    }
}

void dpblank(int x, int y)
{
    int op = 0;
    for (int i = 0; i < (1 << (m + 1)); ++i)
    {
        if (f[x][y][i] > 0)
        {
            decode(i);    
            int u = ch[y - 1], v = ch[m];
            ch[m] = 0;
            ch[y - 1] = 0;
            if (y != m)
                inc(f[x][y + 1][encode()], f[x][y][i]);
            else
                inc(f[x + 1][1][encode()], f[x][y][i]);
            if (u == 0 && v == 0)
            {
                ch[m] = 1;
                ch[y - 1] = 1;
                if (y != m)
                    inc(f[x][y + 1][encode()], f[x][y][i]);
                else
                {
                    ch[m] = 0;
                    inc(f[x + 1][1][encode()], f[x][y][i]);
                }
            }
        }
    }
}

void dpblock(int x, int y)
{
    for (int i = 0; i < (1 << (m + 1)); ++i)
    {
        if (f[x][y][i] > 0)
        {
            decode(i);
            ch[y - 1] = 0;
            ch[m] = 0;
            if (y != m)
                inc(f[x][y + 1][encode()], f[x][y][i]);
            else
                inc(f[x + 1][1][encode()], f[x][y][i]);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 1; j < m + 1; ++j)
            cin >> c[i][j];
    }
    f[1][1][0] = 1;
    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 1; j < m + 1; ++j)
        {
            if (c[i][j] == 1)
                dpblank(i, j);
            else
                dpblock(i, j);
        }
    }
    for (int i = 0; i < (1 << m); ++i)
        inc(ans, f[n + 1][1][i]);
    printf("%lld\n", ans);
}

发表于 2018-01-18 11:17:03 in 题解