AOJ 2431 - House Moving
問題文 : 引越し
解法 :
荷物を動かすために使う体力を最小化する、ということは
動かさない荷物の重量を最大化する、ということと等しい.
ゆえに, 増加する部分列のうち, 重さが最大のものを総重量から引いたものが答えとなる.
荷物の重さを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); }