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 とか使ってもいいかもしれない。
ほかはまあこんなもんでしょう。