JOI春合宿 2012-day4 Bookshelf
問題文 : 本棚
解法 :
にかいどうさんの言うとおり, 昨日解いた「House Moving」と同じ問題でした.(重さがそれぞれ違いますが, あまり関係ない)
ということで, 解説は昨日のもの参照です.
BITでも解けるみたいなので, あとでBITで実装してみます.
コード :
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll seg[1 << 18]; int size; void init(int n) { size = 1; while (size < n) size *= 2; } void update(int k, ll x) { k += size - 1; seg[k] = x; while (k){ k = (k - 1) / 2; seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]); } } ll getMax(int a, int b, int k, int l, int r) { if (r <= a || b <= l){ return (0); } if (a <= l && r <= b){ return (seg[k]); } ll lch = getMax(a, b, k * 2 + 1, l, (l + r) / 2); ll rch = getMax(a, b, k * 2 + 2, (l + r) / 2, r); return (max(lch, rch)); } int main() { ll n; ll data[100000]; ll ans, sum; int pos; scanf("%lld", &n); init(n); sum = 0; for (int i = 0; i < n; i++){ scanf("%lld", &data[i]); data[i] *= 2; sum += data[i]; } ans = 0; for (int i = 0; i < n; i++){ scanf("%d", &pos); update(pos, getMax(1, pos + 1, 0, 0, size) + data[pos - 1]); ans = max(ans, seg[pos + size - 1]); } printf("%lld\n", sum - ans); return (0); }