Overview

We want to remove books from a bookshelf so that the page counts of the remaining books are strictly monotonically increasing. The goal is to minimize the total fee of the removed books. By rephrasing this as “maximize the total fee of the books we keep,” the problem can be solved as a variant of the Longest Increasing Subsequence (LIS).

Analysis

Rephrasing the Problem

Since we want to minimize the total fee of the removed books, thinking in reverse, we should maximize the total fee of the books we keep.

\[\text{Answer} = \text{Total fee of all books} - \text{Maximum total fee of kept books}\]

The condition for “kept books” is that they form a subsequence with strictly increasing page counts. In other words, the problem reduces to finding the subsequence with strictly increasing page counts that maximizes the sum of fees \(C_i\).

Understanding with a Concrete Example

For example, consider the case \(N = 4\), page counts \(A = [3, 1, 4, 2]\), fees \(C = [10, 1, 5, 2]\).

• Keep subsequence \([3, 4]\) (indices 1, 3) → total fee \(10 + 5 = 15\), removal cost \(1 + 2 = 3\)
• Keep subsequence \([1, 4]\) (indices 2, 3) → total fee \(1 + 5 = 6\), removal cost \(10 + 2 = 12\)

As in the former case, by keeping books with higher fees as much as possible, the removal cost becomes smaller.

Naive Approach

Trying all subsets would be \(O(2^N)\), which is far too slow for \(N \leq 5000\). We use dynamic programming (DP).

Algorithm

We use a DP similar to LIS (Longest Increasing Subsequence). However, instead of “maximizing the length,” we “maximize the total fee.”

DP Definition:

\[dp[i] = \text{Maximum total fee among strictly increasing subsequences that end with the book at index } i\]

Transition:

\[dp[i] = C_i + \max\left(\{0\} \cup \{dp[j] \mid j < i \text{ and } A_j < A_i\}\right)\]

• If there exists \(j < i\) satisfying \(A_j < A_i\), add \(C_i\) to the maximum \(dp[j]\) among them.
• If no such \(j\) exists, the subsequence consists of only book \(i\), so \(dp[i] = C_i\).

Answer:

\[\text{Answer} = \sum_{i=1}^{N} C_i - \max_{0 \leq i < N} dp[i]\]

Since \(N \leq 5000\), a double loop with \(O(N^2)\) complexity is fast enough.

Complexity

• Time complexity: \(O(N^2)\) — for each \(i\), we scan \(j = 0, 1, \ldots, i-1\)
• Space complexity: \(O(N)\) — for the DP array and input arrays

Implementation Notes

• Transforming from minimization to maximization is the key insight of this problem. Directly applying DP to “minimize the removal cost” is difficult, but by converting to “maximize the cost of kept books,” it neatly reduces to an LIS-style DP.

• Removing all books (keeping \(0\) books) is also allowed, but since \(C_i \geq 1\), it is always better to keep at least \(1\) book, so the maximum of \(dp\) will never be \(0\). Logically, this poses no issues.

• Since \(C_i\) and the totals can become large, 64-bit integers are required. In Python, there is no integer overflow, so this is not a concern.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    C = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    total_cost = sum(C)
    
    # We want to find a strictly increasing subsequence that maximizes the sum of C
    # (i.e., we keep those books and remove the rest).
    # Answer = total_cost - max sum of C over all strictly increasing subsequences.
    
    # dp[i] = maximum sum of C for a strictly increasing subsequence ending at index i
    # dp[i] = C[i] + max(dp[j] for j < i and A[j] < A[i]), or C[i] if no such j
    
    # N <= 5000, so O(N^2) is fine.
    
    dp = [0] * N
    for i in range(N):
        dp[i] = C[i]
        for j in range(i):
            if A[j] < A[i]:
                dp[i] = max(dp[i], dp[j] + C[i])
    
    max_keep = max(dp)
    print(total_cost - max_keep)

main()

---

This editorial was generated by claude4.6opus-thinking.