ZOJ Monthly, July 2012 K : Watermelon Full of Water

問題概要

N個の重み付き区間[a[i],b[i]), w[i]が与えられる。a = {0,1,2,...,n-1}である。[1,n)を全て被覆するのに必要な最小コストを求める問題。n<10^5。

解法

dp[i] = {i個目の区間を使う場合、それ以降を全て被覆するのに必要な最小コスト}とすると、dp[i] = w[i] + min_{j in [a[i]+1, b[i])} dp[j]となるので、これをrmqで後ろから更新していけばよい。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;

const int64 INF = 1LL<<60;
const int MAX_N = 50010;

int N;
int64 prices[MAX_N], lens[MAX_N];

bool init() {
	if (scanf("%d", &N) == EOF) {
		return false;
	}

	for (int i = 0; i < N; ++i) {
		scanf("%lld", prices + i);
	}
	for (int i = 0; i < N; ++i) {
		scanf("%lld", lens + i);
	}

	return N > 0;
}

int64 solve() {
	rmq.init(N + 1);
	rmq.update(N, 0);
	for (int day = N - 1 ; day >= 0; --day) {
		int64 mini = rmq.ask(day + 1, day + 1 + lens[day]);
		rmq.update(day, mini + prices[day]);
	}

	return rmq.getElement(0);
}

int main() {
	for (;init();) {
		printf("%lld\n", solve());
	}
	return 0;
}