PKU JudgeOnline 3254 - Corn Fields

問題

http://poj.org/problem?id=3254

Farmer Johnはの牧草地を購入しました. 各牧草地のマスは肥沃であるか, 不毛であるかのどちらかです.
ここでFarmer Johnは牛たちのためにとうもろこしを栽培することにしました. 一マスで育てられるとうもろこしは一つだけで, なおかつそれぞれのマスは一つの牛だけに割り当てられることになります. 牛たちは窮屈な状態で食事をするのが嫌なので, 互いに辺を共有するようなマス同士ではとうもろこしを同時に育てることはできません. また当然のことながら不毛な土地ではとうもろこしを育てることができません.
このような条件下でとうもろこしを育てるマスを選ぶ方法はいくつあるでしょうか. 100000000で割った余りを答えてください.

解法

蟻本p.179とほとんど同じ問題なので解法は省略. 蟻本では貰うDPで実装していましたが, 今回は配るDPで実装しました.

ソースコード

#include <iostream>
using namespace std;

const int kMAX_M = 13;
const int kMAX_N = 13;
const int kMOD = 100000000;

int N, M;

int pasture[kMAX_M][kMAX_N];
int dp[kMAX_M][kMAX_N][1 << kMAX_N];

void Solve() {
    dp[0][0][0] = 1;
    for (int row = 0; row < M; row++) {
        for (int col = 0; col < N; col++) {
            for (int used = 0; used < (1 << N); used++) {
                if (dp[row][col][used] == 0) continue;

                if (col == N - 1) {
                    dp[row + 1][0][used & ~(1 << col)] += dp[row][col][used];
                    dp[row + 1][0][used & ~(1 << col)] %= kMOD;
                } else {
                    dp[row][col + 1][used & ~(1 << col)] += dp[row][col][used];
                    dp[row][col + 1][used & ~(1 << col)] %= kMOD;
                }

                if (((used >> col) & 1) || (col > 0 && ((used >> (col - 1)) & 1)) ||
                        !pasture[row][col]) {
                    continue;
                }

                if (col == N - 1) {
                    dp[row + 1][0][used | (1 << col)] += dp[row][col][used];
                    dp[row + 1][0][used | (1 << col)] %= kMOD;
                } else {
                    dp[row][col + 1][used | (1 << col)] += dp[row][col][used];
                    dp[row][col + 1][used | (1 << col)] %= kMOD;
                }
            }
        }
    }
    int ans = 0;
    for (int used = 0; used < (1 << N); used++) {
        ans += dp[M][0][used];
        ans %= kMOD;
    }
    cout << ans << endl;
}

int main() {
    cin >> M >> N;

    for (int row = 0; row < M; row++) {
        for (int col = 0; col < N; col++) {
            cin >> pasture[row][col];
        }
    }

    Solve();

    return 0;
}

感想

なんで蟻本では貰うDPで実装しているんだろうと思いましたが, ようやく理由がわかりました(完)