Bookshelf
こどふぉなんてなかったんや....あのDiv1Bとかbookshelfやってたら絶対解けたよね。
考えると重みが付いた最大増加部分列を求めると良いことがわかって、segtreeを使って処理。
(重さが全部1の時はよくあるやつ)
重さの入力のが、並んでる順番に与えられてるんだと勝手に思って苦労した。問題文はちゃんと読みましょう。
#include <cstdio> #include <algorithm> using namespace std; #define rep(i, n) for(int i = 0; i < (int)n; ++i) typedef long long ll; int n; ll dp[100010]; int hon[100010], w[100010]; ll sum, ret; int sz = 1LL; ll dat[1 << 18]; void init(int n_){ while(n_ > sz) sz *= 2LL; rep(i, sz * 2 - 1) dat[i] = 0; } inline void update(int k, ll a){ k += sz - 1; dat[k] = a; while(k > 0){ k = (k - 1) / 2; dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]); } } ll query(int a, int b, int k = 0, int l = 0, int r = sz){ if(a <= l && r <= b) return dat[k]; else if(r <= a || b <= l) return 0; ll lch = query(a, b, k * 2 + 1, l, (l + r) / 2); ll rch = query(a, b, k * 2 + 2, (l + r) / 2, r); return max(lch, rch); } int main(){ scanf("%d", &n); rep(i, n){ scanf("%d", &w[i]); sum += w[i]; } rep(i, n){ scanf("%d", &hon[i]); --hon[i]; } bool f = true; init(n); rep(i, n){ if(w[i] != 1){ f = false; break; } } if(f){ fill(dp, dp + n, INT_MAX); rep(i, n) *lower_bound(dp, dp + n, hon[i]) = hon[i]; int piv = lower_bound(dp, dp + n, INT_MAX) - dp; printf("%lld\n", (sum - piv) * 2); return 0; } dp[hon[0]] = w[hon[0]]; update(hon[0], dp[hon[0]]); for(int i = 1; i < n; i++){ ll ma = query(0, hon[i]); dp[hon[i]] = ma + w[hon[i]]; update(hon[i], (ll)dp[hon[i]]); } rep(i, n) ret = max(ret, dp[i]); printf("%lld\n", (sum - ret) * 2LL); return 0; }