概要

本をいくつか取り除いて残った本のページ数が狭義単調増加になるようにし、取り除く手数料の合計を最小化する問題です。

考察

この問題は、元の本の列から部分列を選び、その部分列のページ数が狭義単調増加になるようにする問題と等価です。残す本の手数料の合計を最大化すれば、取り除く手数料の合計は最小化されます。

素朴なアプローチとしては、全ての部分列を調べて条件を満たすものを探す方法が考えられますが、部分列の数は \(2^N\) 通りあるため、\(N\) が最大5000の場合には計算量が膨大になり現実的ではありません。

そこで、動的計画法（DP）を用いて効率的に解くことを考えます。狭義単調増加部分列の中で手数料の合計が最大のものを求める問題は、最長増加部分列（LIS）問題の拡張版と見なせます。

アルゴリズム

動的計画法を用いて、各位置 \(i\) を終点とする狭義単調増加部分列の中で、手数料の合計の最大値を求めます。

具体的には： - \(\text{dp}[i]\)：\(i\) 番目の本を最後の要素とする狭義単調増加部分列の手数料の合計の最大値 - 各 \(i\) について、\(j < i\) かつ \(A[j] < A[i]\) を満たす全ての \(j\) について \(\text{dp}[j]\) の最大値を求め、それに \(C[i]\) を加えた値を \(\text{dp}[i]\) とします

最終的に、全ての \(\text{dp}[i]\) の最大値 \(\text{max\_keep}\) を求め、総手数料から \(\text{max\_keep}\) を引くことで、最小の取り除き手数料を得ます。

計算量

• 時間計算量: \(O(N^2)\)
  • 外側のループが \(N\) 回、内側のループが最大 \(N\) 回実行されるため
• 空間計算量: \(O(N)\)
  • DP配列のサイズが \(N\) であるため

実装のポイント

• 総手数料の合計を事前に計算しておく

• DPの初期化では、各位置の初期値はその本単体の手数料となる（\(C[i]\) のみの部分列）

• 内側のループでは、\(A[j] < A[i]\) を満たす場合のみ処理を行う

• \(N=0\) の場合の処理を忘れずに行う

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    C = list(map(int, data[1+n:1+2*n]))
    
    total_cost = sum(C)
    INF = 10**18
    dp = [0] * (n+1)
    
    for i in range(n):
        max_val = 0
        for j in range(i):
            if A[j] < A[i]:
                if dp[j] > max_val:
                    max_val = dp[j]
        dp[i] = max_val + C[i]
    
    max_keep = max(dp) if n > 0 else 0
    ans = total_cost - max_keep
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。