読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

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

AOJ 2431 - House Moving

AOJ データ構造 動的計画法

問題文 : 引越し

解法 :
荷物を動かすために使う体力を最小化する、ということは
動かさない荷物の重量を最大化する、ということと等しい.
ゆえに, 増加する部分列のうち, 重さが最大のものを総重量から引いたものが答えとなる.

荷物の重さをkとし, dp[k] -> 重さkの荷物までの重量の最大値, とすると

dp[k] = max(dp[1] ~ dp[k - 1]) + k

となるので, 入力された順にこのdpテーブルを埋め, 総重量からdp配列の最大値を引いたものを答えとして出力する.

コード :

#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 ans;
	int data;
	
	scanf("%lld", &n);
	
	init(n);
	ans = 0;
	
	for (int i = 0; i < n; i++){
		scanf("%d", &data);
		update(data, getMax(1, data + 1, 0, 0, size) + data);
		ans = max(ans, seg[data + size - 1]);
	}
	
	printf("%lld\n", n * (n + 1) / 2 - ans);
	
	return (0);
}