はまやんはまやんはまやん

hamayanhamayan's blog

積み荷の配置 [パソコン甲子園2017 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0363?year=2017

前提知識

考察過程

1. 横幅4mというのが重要に見える
2. 今回は荷物が置かれているかどうかというのが重要なので、bitdpできそう
3. 丁度1つ上の行の状態だけ持てばいいのでbitdpで確定かな?
4. O(H2^8)も大丈夫そうですね

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0363/review/3136527/hamayanhamayan/C++14

dp[y][msk] := y行目まで確定していて、y行目の埋まり具合がmskのときに置ける荷物の最大個数
mskは荷物がおけない区間にビットが立っている必要があるので、check関数で使えるmskか確認しよう。
あとは荷物を置いていくだけだが、注意点が1行に2つ置く場合の遷移をしっかり用意することである。
(親切にもサンプルにある)

int H, N;
int ng[10101][4];
int dp[10101][1 << 4];
//---------------------------------------------------------------------------------------------------
int check(int y, int msk) {
    rep(x, 0, 4) if (ng[y][x]) if (!(msk & (1 << x))) return 0;
    return 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> N;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        ng[y][x] = 1;
    }

    rep(y, 0, H - 1) rep(msk, 0, 1 << 4) if(check(y, msk)) {
        rep(msk2, 0, 1 << 4) if (check(y + 1, msk2)) {
            // 1個置く
            rep(x, 0, 3) {
                if (msk & (1 << x)) continue;
                if (msk & (1 << (x+1))) continue;
                if (msk2 & (1 << x)) continue;
                if (msk2 & (1 << (x + 1))) continue;

                chmax(dp[y + 1][msk2 + (1 << x) + (1 << (x + 1))], dp[y][msk] + 1);
            }
            // 2個置く
            if (msk == 0 and msk2 == 0) chmax(dp[y + 1][(1 << 4) - 1], dp[y][0] + 2);
            chmax(dp[y + 1][msk2], dp[y][msk]);
        }
    }

    int ans = 0;
    rep(msk, 0, 1 << 4) if (check(H - 1, msk)) chmax(ans, dp[H - 1][msk]);
    cout << ans << endl;
}