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