の計算量までなら比較的すぐできる!
問題概要
街 があって、街 間の行き来には だけの通行料がかかる。
回の市場がそれぞれ街 で行われ、 円えられる。
最初、無限の所持金を持っている。いくつかの市場に参加する (全く参加しなくてもよい) ことで得られる、所持金の変化額の最大値を求めよ。
制約
考えたこと
次の DP ができる。
dp[ i + 1 ][ j ]
← 市場 を終えた直後に、街 にいるときの所持金の変化額の最大値
さて、この配列は、基本的には の部分のみ更新すればよい。このことに着目して、in-place 化しよう (in-place 化については次の記事を参照)。
このとき、dp[T[i]]
の更新は、セグ木でできる。ただし、通行料を上手に扱うために、次の 2 本のセグ木をもつ
minus[j]
← その時点で市場 にいるときの、所持金の変化額の最大値から、 を引いたものplus[j]
← その時点で市場 にいるときの、所持金の変化額の最大値に、 を足したもの
これによって、DP 更新がスムーズにできるようになる。詳しくはコードにて。
コード
#include <bits/stdc++.h> using namespace std; // Segment Tree template<class Monoid> struct SegmentTree { using Func = function<Monoid(Monoid, Monoid)>; // core member int N; Func OP; Monoid IDENTITY; // inner data int log, offset; vector<Monoid> dat; // constructor SegmentTree() {} SegmentTree(int n, const Func &op, const Monoid &identity) { init(n, op, identity); } SegmentTree(const vector<Monoid> &v, const Func &op, const Monoid &identity) { init(v, op, identity); } void init(int n, const Func &op, const Monoid &identity) { N = n; OP = op; IDENTITY = identity; log = 0, offset = 1; while (offset < N) ++log, offset <<= 1; dat.assign(offset * 2, IDENTITY); } void init(const vector<Monoid> &v, const Func &op, const Monoid &identity) { init((int)v.size(), op, identity); build(v); } void pull(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); } void build(const vector<Monoid> &v) { assert(N == (int)v.size()); for (int i = 0; i < N; ++i) dat[i + offset] = v[i]; for (int k = offset - 1; k > 0; --k) pull(k); } int size() const { return N; } Monoid operator [] (int i) const { return dat[i + offset]; } // update A[i], i is 0-indexed, O(log N) void set(int i, const Monoid &v) { assert(0 <= i && i < N); int k = i + offset; dat[k] = v; while (k >>= 1) pull(k); } // get [l, r), l and r are 0-indexed, O(log N) Monoid prod(int l, int r) { assert(0 <= l && l <= r && r <= N); Monoid val_left = IDENTITY, val_right = IDENTITY; l += offset, r += offset; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) val_left = OP(val_left, dat[l++]); if (r & 1) val_right = OP(dat[--r], val_right); } return OP(val_left, val_right); } Monoid all_prod() { return dat[1]; } // get max r such that f(v) = True (v = prod(l, r)), O(log N) // f(IDENTITY) need to be True int max_right(const function<bool(Monoid)> f, int l = 0) { if (l == N) return N; l += offset; Monoid sum = IDENTITY; do { while (l % 2 == 0) l >>= 1; if (!f(OP(sum, dat[l]))) { while (l < offset) { l = l * 2; if (f(OP(sum, dat[l]))) { sum = OP(sum, dat[l]); ++l; } } return l - offset; } sum = OP(sum, dat[l]); ++l; } while ((l & -l) != l); // stop if l = 2^e return N; } // get min l that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int min_left(const function<bool(Monoid)> f, int r = -1) { if (r == 0) return 0; if (r == -1) r = N; r += offset; Monoid sum = IDENTITY; do { --r; while (r > 1 && (r % 2)) r >>= 1; if (!f(OP(dat[r], sum))) { while (r < offset) { r = r * 2 + 1; if (f(OP(dat[r], sum))) { sum = OP(dat[r], sum); --r; } } return r + 1 - offset; } sum = OP(dat[r], sum); } while ((r & -r) != r); return 0; } // debug friend ostream& operator << (ostream &s, const SegmentTree &seg) { for (int i = 0; i < (int)seg.size(); ++i) { s << seg[i]; if (i != (int)seg.size() - 1) s << " "; } return s; } }; int main() { long long N, C, M; cin >> N >> C >> M; vector<long long> T(M), P(M); for (int i = 0; i < M; ++i) { cin >> T[i] >> P[i]; --T[i]; } const long long INF = 1LL<<60; auto op = [&](long long a, long long b) -> long long { return max(a, b); }; SegmentTree<long long> minus(N, op, -INF), plus(N, op, -INF); minus.set(0, 0), plus.set(0, 0); for (int i = 0; i < M; ++i) { long long left = plus.prod(0, T[i]) - C * T[i]; long long right = minus.prod(T[i], N) + C * T[i]; long long val = max(left, right) + P[i]; minus.set(T[i], max(minus[T[i]], val - C * T[i])); plus.set(T[i], max(plus[T[i]], val + C * T[i])); } long long res = 0; for (int i = 0; i < N; ++i) { res = max(res, minus[i] + C * i); } cout << res << endl; }