Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}