この問題は DP により解くことができます。

元の問題は取り除く本の手数料を最小化する問題ですが、先に全ての本を取り除いてから手数料と本を返してもらうと考えることで、残す本の手数料を最大化する問題になります。以下、この方針で考えます。

\(0\) 番目の本として、ページ数 \(0\) 、手数料 \(0\) の本があるとし、この本は必ず残すとしても答えは変わりません。よってそのように仮定します。

\(\mathrm{DP}[i]\) を「残す本のうち最も右にあるものが \(i\) 番目の本であるときの、残す本の手数料の最大値」と定めます。 このとき、\(i\) のすぐ左にある残す本が何番目の本であるかを考えることで、

\(\displaystyle \mathrm{DP}[i] = \max_{\substack{0\leq j < i \\ A_j < A_i} }(\mathrm{DP}[j]+C[i])\)

となります。この DP は状態数 \(O(N)\) 、遷移の計算が \(O(N)\) ででき、全体を \(O(N^2)\) で計算することができます。求める答えは \(\sum_{i=1}^{N}C_i - \max_{0\leq i \leq N}\mathrm{DP}[i]\) となります。

なおこの問題はセグメントツリーを用いることで \(O(N\log N)\) で解くこともできます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int>a(n+1), c(n+1);
  for(int i=1; i<=n; i++) cin >> a[i];
  for(int i=1; i<=n; i++) cin >> c[i];

  vector<long long> dp(n+1, (long long)-1e18);
  dp[0] = 0;
  for(int i=1; i<=n; i++){
    for(int j=0; j<i; j++){
      if(a[j] < a[i]){
        dp[i] = max(dp[i], dp[j] + c[i]);
      }
    }
  }

  long long ans = 0;
  for(int i=1; i<=n; i++){
    ans += c[i];
  }
  ans -= *max_element(dp.begin(), dp.end());
  cout << ans << endl;
}

実装例 (Python)

N = int(input())
A = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

dp = [-10**18] * (N+1)
dp[0] = 0
for i in range(1, N+1):
  for j in range(i):
    if A[j] < A[i]:
      dp[i] = max(dp[i], dp[j] + C[i])

print(sum(C) - max(dp))