AtCoder Beginner Contest 008 D - 金塊ゲーム

問題

abc008.contest.atcoder.jp

解法

まず 99 点の部分点解法を考えてみます。

一回金塊を取ると, 長方形は 4 つに分断されます。分断された各長方形からは, 別れた他の長方形の金塊を取りに行くことは出来ません。よって, 区間 dp 的に, dp[dlX][dlY][urX][urY] = (左下の頂点と右下の頂点を決めた時, その中で取れる金塊の最大値) とすれば, 問題が解けます。

満点解法では, この dp を上手く圧縮します。よく考えると, dlX, ... として考えられるのは, 各回収装置の座標を (xi, yi) として,

• (xi, yi)
• (xj, yi)
• (0, yi), (xi, 0), (W, yi), (xi, H)

のみであるので, これらを座標圧縮(?)しておきましょう。これらの組み合わせとして考えられるのは, O(N^2) 程度で, dp[dl][ur] = (左下の頂点が dl, 右上の頂点が ur の場合の回収できる金塊の最大値) とすれば答えが得られます。

const int MAX = 2000;
ll dp[MAX][MAX];
pii pos[MAX];
int X[40], Y[40];
int N;

ll dfs(int dl, int ur, map<pii, int>& mp) {
    ll& ret = dp[dl][ur];
    if (ret >= 0) return ret;
    ret = 0;
    int x0 = pos[dl].first, y0 = pos[dl].second;
    int x1 = pos[ur].first, y1 = pos[ur].second;
    for (int i = 1; i < N-1; i++) {
        if (x0 < X[i] && X[i] < x1 && y0 < Y[i] && Y[i] < y1) {
            ll tmp = (x1-x0-1) + (y1-y0-1) - 1;
            // 左下
            tmp += dfs(dl, mp[pii(X[i], Y[i])], mp);
            // 左上
            tmp += dfs(mp[pii(x0, Y[i])], mp[pii(X[i], y1)], mp);
            // 右下
            tmp += dfs(mp[pii(X[i], y0)], mp[pii(x1, Y[i])], mp);
            // 右上
            tmp += dfs(mp[pii(X[i], Y[i])], ur, mp);
            ret = max(ret, tmp);
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, H;
    cin >> W >> H;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> X[i] >> Y[i];
    X[0] = Y[0] = 0;
    X[N+1] = W+1, Y[N+1] = H+1;
    N += 2;
    map<pii, int> mp;
    for (int i = 0; i < N; i++) {
        mp[pii(X[i], Y[i])] = 0;
        for (int j = i+1; j < N; j++) {
            mp[pii(X[i], Y[j])] = 0;
            mp[pii(X[j], Y[i])] = 0;
        }
    }
    int k = 0;
    for (auto& p : mp) {
        p.second = k;
        pos[k] = p.first;
        k++;
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(mp[pii(0, 0)], mp[pii(W+1, H+1)], mp) << endl;
    return 0;
}