[AOJ] No. 0363 積み荷の配置

2019年12月17日

問題

方針

\( i \) 列目に荷物が置けるかどうかは \( i – 1 \) 列目と \( i \) 列目を調べれば良いので、動的計画法を行います。各列の状態は荷物か置けるマスがあるかどうかの \( 2 \) 通りであり \( 4 \)マスあるので、全体で \( 16 \) 通りあります。なので、bitDP を行います。

更新式

\( d(i, j) \) を \( i \) 列目のマスが \( j \) であるときの置くことができる荷物の最大数とします。ここで、\( j \) は \( 2 \) 進数で表現されたマスの状態とします。\( i \) 列目のマスの状態を \( b_i\) とすると、初期値は \( d(0, b_0) = 0\) とし、それ以外は、\( d(i, j) = -1 \) とします。

荷物の置き方は、\( 1100, 0110, 0011, 1111\) の \( 4 \) 通りあり、荷物を置かないパターンは \( 0000 \) と表します。

\( d(i – 1, j) \neq -1\) のとき、遷移できる状態を考えます。ここで、\( c_1 = 1100 \) とします。  \( i -1, \ i\) 列目に、\( c_1 \) の置き方ができるとき、\( j \wedge c_1 = 0 \) ならば、\( d(i, b_i \vee c_1) \leftarrow d(i -1, j) + 1 \) と更新することができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int c[50000][4]{};

bool check(int i, int j) {
    for (int k = 0; k < 4; k++) {
        int t = 1<<k;
        if ((t & j) != 0 && c[i][k] == 1) return false;
    }
    return true;
}

int main() {
    int H, N;
    cin >> H >> N;
    int x[N], y[N];
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        c[y[i]][x[i]] = 1;
    }

    int d[H][16]{};
    fill(d[0], d[H], -1);
    int a = 0;
    
    for (int i = 0; i < 4; i++) {
        if (c[0][i] == 1) a += (1<<i);
    }
    d[0][a] = 0;
    
    // 0000 1100 0110 0011 1111
    // 0    3    6    12    15
    for (int i = 1; i < H; i++) {
        int t = 0; // i-1 列目の配置
        int u = 0; // i列目の配置
        for (int j = 0; j < 4; j++) {
            if (c[i - 1][j] == 1) t += (1<<j);
            if (c[i][j] == 1) u += (1<<j);
        }
        // 何も置かない
        for (int j = 0; j < 16; j++) {
            d[i][u] = max(d[i][u], d[i - 1][j]);
        }
        
        for (int j = 0; j < 16; j++) {
            if (d[i - 1][j] < 0) continue;
            for (int k = 0; k < 3; k++) {
                int c = (1<<k) + (1<<(k + 1));
                if (check(i - 1, c) && check(i, c) && (j & c) == 0) {
                    d[i][u | c] = max(d[i][u | c], d[i - 1][j] + 1);
                }
            }
            if (check(i, 15) && check(i - 1, 15) && (j & 15) == 0) {
                d[i][15] = max(d[i][15], d[i - 1][j] + 2);
            }
        }
    }
    int v = 0;
    for (int i = 0; i < 16; i++) {
        v = max(v, d[H - 1][i]);
    }
    cout << v << "\n";
    
    return 0;
}