概要

「取り除くコスト最小化」は「残す本（狭義増加部分列）に対応する“取り除かずに済むコスト”最大化」に言い換えられます。重み付き最長増加部分列（最大重み増加部分列）を高速に求めます。

考察

残った本は並び替えできないので、残す本の集合は元の順序を保った部分列になります。条件はページ数が狭義単調増加、つまり \(A_{i_1} < A_{i_2} < \cdots\) を満たす必要があります。

ここで目的は「取り除く本の手数料合計の最小化」ですが、全手数料の総和を \(S=\sum C_i\) とすると、

• 取り除く本に払う手数料 ＝ \(S - (\text{取り除かずに済んだ手数料})\)
• 取り除かずに済んだ手数料 ＝ 「残した本の \(C\) の合計」

です。よって問題は次のように言い換えられます：

ページ数が狭義増加となるように本を残すとき、残した本の \(C\) 合計を最大化せよ。
答えは \(S - (\text{最大値})\)。

素朴には \(dp[i] = i\) 番目を最後に残すときの最大合計として
\(dp[i] = C_i + \max\{dp[j] \mid j<i, A_j < A_i\}\)
を計算すると \(O(N^2)\) になり、\(N=5000\) だとギリギリ/実装次第で重くなりがちです（さらに余裕を持つなら改善したい）。
これを「\(A_j < A_i\) を満たす範囲の最大値」を高速に取れるデータ構造で加速します。

アルゴリズム

1. 座標圧縮

\(A_i\) は最大 \(10^9\) なので、そのままでは配列添字に使いにくいです。
\(A\) のユニーク値をソートして、各 \(A_i\) を \(1..M\) の順位 \(r_i\) に変換します（座標圧縮）。

2. BIT（Fenwick Tree）で「prefix 最大」を管理

BIT は通常は prefix 和を扱いますが、演算を「最大」に置き換えることで

• query(x)：圧縮値が \(x\) 以下の範囲の \(dp\) 最大値
• update(x, v)：位置 \(x\) の値を \(\max(\text{現在}, v)\) で更新

が \(O(\log M)\) でできます。

3. DP 遷移

本 \(i\) を「残す」場合、直前に残せるのは \(A\) がより小さい本なので、 圧縮順位を \(r\) とすると

• \(\text{bestPrev} = \max\{dp \mid \text{順位} \le r-1\} = \text{query}(r-1)\)
• \(dp = \text{bestPrev} + C_i\)

を計算し、update(r, dp) します。全体の最大値 best が「残せる手数料合計の最大」です。

最後に答えは \(\sum C_i - best\) となります。

計算量

• 時間計算量: \(O(N \log N)\)（座標圧縮のソート \(O(N\log N)\)＋各要素のBIT操作 \(O(\log N)\)）
• 空間計算量: \(O(N)\)（圧縮配列・BIT）

実装のポイント

• 狭義増加なので、遷移は必ず query(r-1)（同じページ数はつなげない）。

• BIT は「和」ではなく「最大」を持つ実装にする（bit[i] = max(bit[i], v)）。

• \(C_i\) や合計は最大で \(10^9 \times 5000\) になり得るため、言語によっては 64bit 整数が必要（Python は問題なし）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    A = data[1:1+n]
    C = data[1+n:1+2*n]

    xs = sorted(set(A))
    m = len(xs)
    rank = {v: i+1 for i, v in enumerate(xs)}  # 1-indexed

    bit = [0] * (m + 2)

    def update(i, v):
        while i <= m:
            if v > bit[i]:
                bit[i] = v
            i += i & -i

    def query(i):
        res = 0
        while i > 0:
            if bit[i] > res:
                res = bit[i]
            i -= i & -i
        return res

    total = sum(C)
    best = 0
    for a, c in zip(A, C):
        r = rank[a]
        dp = query(r - 1) + c
        update(r, dp)
        if dp > best:
            best = dp

    print(total - best)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。