https://yukicoder.me/problems/no/777
前提知識
- 座標圧縮(座圧)
- 動的計画法
- 区間maxのセグメントツリーによるDP高速化
考察過程
1. 今回の問題のように包含関係を使うものは、上における場合にケーキの間に有効辺を貼るとDAGになるので、DPになりやすい傾向がある
2. DPで考えてみると、遷移の数が多いので、なんとかしたくなる
3. こういうときの策としては色々あるが「遷移をへらす」「遷移をまとめる」で考えてみる
4. 「遷移をへらす」より「遷移をまとめる」方が簡単なので、こっちで考える
5. あるケーキへの遷移は、Aが小さく、Bも小さいものだが、これはとある区間にできそうなので、まとめられそう
6. ここでDPのテクを2つ使うことでなんとかする「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」と「配列を使い回すことでメモリ使用量を節約する(500^3は256MBに乗らない)」
7. このテクを使うことを考えると「dp[i] := 一番上の奥行きがiのケーキの最大カロリー」を更新していくことで答えが出せる
解法
https://yukicoder.me/submissions/307842
DPをする。
dp[i] := 一番上の奥行きがiのケーキの最大カロリー
このDPの更新のために、奥行きを座圧しておこう。
DPのテクとして「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」を使う。
Aが小さい方からまとめて処理して、DP更新をする。
この処理のために「buf[a] := A[i]=aであるiの配列」を作って、aの小さい方から処理をしていくことにする。
こうしておくことで、これより前に処理されたケーキはすべてAが小さい条件を満たすことになる。
次に「配列を使い回すことでメモリ使用量を節約する(500^3は256MBに乗らない)」を使う。
あるAについて、ケーキを使うかどうか考えていく。
奥行きがb[i]であるケーキは、「dp[j](j<b)の最大値+C[i]」によってdp[i]を更新できる。
つまり、更新される要素は各ケーキについて1つだけになる。
なので、dp配列を使いまわすことで、更新を高速に行える。
あとは、「dp[j](j<b)の最大値」を高速に求める方法だが、これはdpをセグメントツリーにしておけば実現できる。
int N, A[201010], B[201010], C[201010]; SegTree<ll, 1 << 18> st; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i] >> B[i] >> C[i]; vector<int> v; rep(i, 0, N) v.push_back(B[i]); sort(all(v)); v.erase(unique(all(v)), v.end()); rep(i, 0, N) B[i] = lower_bound(all(v), B[i]) - v.begin(); map<int, vector<int>> buf; rep(i, 0, N) buf[A[i]].push_back(i); fore(p, buf) { auto& v = p.second; vector<pair<int, ll>> nxt; fore(i, v) { ll c = st.get(0, B[i]) + C[i]; nxt.push_back({ B[i], c }); } fore(p, nxt) st.update(p.first, max(p.second, st[p.first])); } ll ans = st.get(0, N); cout << ans << endl; }