AOJ 2787 Pipe Fitter and the Fierce Dogs

解法

一番上の行のすべての家は special pipe 確定だから、(W + 1) / 2 > K なら不可能であり、それ以外は可能である。
それ以外については、一旦 special pipe を使わないとして考えよう。
すると、以下の dp で解くことができる。
dp[i][j][k] := i 行目 j 列目の家まで考えた時に、使った家の状態が k である場合の最小コスト
i, j は家がないところを圧縮しておく(MLEするため)。
家の状態 k についてだが、これは (左上が使われている) or (真上が使われている) の2通りしかないので、丁寧に場合分けして十分。

こうして求まった答えを X とする。
もし犬を完全に回避できれば、((H - 1) / 2) * ((W + 1) / 2) のコストで common pipe を配置できる。
もし X がこれを超えていれば、その分だけ犬のマスに pipe を配置したことがわかる。
あとは、残っている special pipe を犬のマスに優先的に割りあて、それでも special pipe が残っているなら、その数だけ答えから引いてやれば良い。
サンプルにもあるが、引きすぎて負の値にならないようにすること。

計算量は O(wh) となる。

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
const int inf = 1e9;
 
int main() {
    int w, h, k; cin >> w >> h >> k;
    int n; cin >> n;
    vector<vector<int>> cost(w, vector<int>(h / 2, 1));
    for(int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;
        x--, y--;
        if(y % 2 == 0) continue;
        cost[x][y / 2] = 2;
    }
 
    k -= (w + 1) / 2;
    if(k < 0) {
        cout << -1 << endl;
        return 0;
    }
 
    const int hz = (h - 1) / 2, wz = (w + 1) / 2;
    vector<vector<int>> dp(wz + 1, vector<int>(2, inf));
    dp[0][0] = 0;
    for(int y = 0; y < hz; ++y) {
        for(int x = 0; x < wz; ++x) {
            if(dp[x][0] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][0] + cost[x * 2][y]);
                if(x != wz - 1) {
                    dp[x + 1][1] = min(dp[x + 1][1], dp[x][0] + cost[x * 2 + 1][y]);
                }
            }
            if(dp[x][1] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][1] + cost[x * 2 - 1][y]);
            }
        }
        const int ns = dp[wz][0];
        for(int x = 0; x <= wz; ++x) {
            for(int S = 0; S < 2; ++S) {
                dp[x][S] = inf;
            }
        }
        dp[0][0] = ns;
    }
 
    int ans = dp[0][0];
    const int tcnt = min(k, ans - hz * wz);
    const int ocnt = max(0, k - tcnt);
    ans = max(0, ans - tcnt * 2 - ocnt);
    cout << ans << endl;
}

感想

cost の2次元配列が贅沢すぎるから、map とか使ってもいいかもしれない。
ほかはまあこんなもんでしょう。