AOJ 0389 Dungeon 2
解法
木DP。つらい。
以下自分の解き方を書くけど、他の人のコード読む限り状態数はまだ減らせそう？
すくなくともテーブルでもつ必要のある状態は減らせると思う。まあいいか。
まず、部分木の根が全体としてどういう使われ方をしうるかを丁寧に見よう。
適当に考えると少なくとも以下の4通り考えればよさそう。
- 場合1：根ノードが始点。終点は（部分木の）どこでも
- 場合2：根ノードが終点。始点は（部分木の）どこでも
- 場合3：根ノードが始点かつ終点
- 場合4：根ノードはウォークの中間頂点
場合1：根ノードが始点
子から場合3のもので得をするものを使う。
また、子のうち一つは場合1のものを選択して良い。
場合2：根ノードが終点
子から場合3のもので得をするものを使う。
また、子のうち1つは場合2のものを使って良い。
ほとんど場合1と同じ。
場合3
子から場合3のもので得をするものを使う。以上
場合4
これはちょっと面倒だった。大きく分けて2通りあるからである。
- 場合3の子ノードで得をするものを使う。子のうち1つは場合4のものを選択
- 場合3の子ノードで特をするものを使う。子のうち2つは場合2と場合1を1つずつ選択
1つ目については、例えば子 v が中間頂点とするウォークを考えると、v から今の頂点に寄り道してまた子 v に戻るようなウォークがあるからである。
2つ目は、子 c1 から今の頂点に移ってきて、また別の子 c2 に入っていくようなウォークである。
2つ目はいいけど1つ目のを忘れやすい気がする。状態の持ち方によるかも。
計算量は O(nlogn)
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; constexpr int inf = 1e9; int main() { int n; cin >> n; vector<int> p(n); vector<vector<int>> g(n); for(int i = 0; i < n; ++i) { cin >> p[i]; } for(int i = 0; i < n - 1; ++i) { int s, t; cin >> s >> t; g[s - 1].push_back(t - 1); g[t - 1].push_back(s - 1); } // 0: start, 1: last, 2: start & last, 3: inter int ans = -inf; vector<vector<int>> dp(n, vector<int>(4, -inf)); function<void(int, int)> dfs = [&] (int v, int par) { dp[v][0] = dp[v][1] = dp[v][2] = dp[v][3] = p[v]; vector<int> ch0, ch1, ch2; vector<pii> sub0, sub1; int sum2 = 0, max_sub3 = 0; for(auto to : g[v]) { if(to == par) continue; dfs(to, v); ch0.push_back(max(0, dp[to][0] - 1)); ch1.push_back(max(0, dp[to][1] - 1)); ch2.push_back(max(0, dp[to][2] - 2)); sub0.emplace_back(ch0.back() - ch2.back(), to); sub1.emplace_back(ch1.back() - ch2.back(), to); max_sub3 = max(max_sub3, max(0, dp[to][3] - 2) - ch2.back()); sum2 += ch2.back(); } const int sz = ch0.size(); sort(rbegin(sub0), rend(sub0)); sort(rbegin(sub1), rend(sub1)); for(int i = 0; i < sz; ++i) { dp[v][0] = max(dp[v][0], sum2 + ch0[i] - ch2[i] + p[v]); dp[v][1] = max(dp[v][0], sum2 + ch1[i] - ch2[i] + p[v]); } dp[v][2] = max(dp[v][2], sum2 + p[v]); // inter dp[v][3] = max(dp[v][3], sum2 + max_sub3 + p[v]); if(sz >= 2) { for(int i = 0; i < 2; ++i) { for(int j = 0; j < 2; ++j) { if(i == j || sub0[i].second == sub1[j].second) continue; dp[v][3] = max(dp[v][3], sum2 + sub0[i].first + sub1[j].first + p[v]); } } } ans = max(ans, *max_element(begin(dp[v]), end(dp[v]))); }; dfs(0, -1); cout << ans << endl; }
感想
木DP、毎回頭壊れるんだけどどうすればええんや…
なんか遷移が難しいのばっかりなんだよね。実装が悪いのかなあ。
