Overview

This is a problem where we remove some books so that the page counts of the remaining books are strictly monotonically increasing, and we minimize the total removal fee.

Analysis

This problem is equivalent to selecting a subsequence from the original sequence of books such that the page counts of the subsequence are strictly monotonically increasing. If we maximize the total fee of the books we keep, then the total fee of the books we remove is minimized.

A naive approach would be to examine all subsequences and find those that satisfy the condition, but since there are \(2^N\) possible subsequences, this is impractical when \(N\) can be up to 5000 due to the enormous computational cost.

Therefore, we consider solving this efficiently using dynamic programming (DP). The problem of finding the strictly increasing subsequence with the maximum total fee can be viewed as an extension of the Longest Increasing Subsequence (LIS) problem.

Algorithm

Using dynamic programming, we find the maximum total fee among all strictly increasing subsequences ending at each position \(i\).

Specifically: - \(\text{dp}[i]\): the maximum total fee of a strictly increasing subsequence whose last element is the \(i\)-th book - For each \(i\), we find the maximum value of \(\text{dp}[j]\) over all \(j\) satisfying \(j < i\) and \(A[j] < A[i]\), and set \(\text{dp}[i]\) to that value plus \(C[i]\)

Finally, we find the maximum value \(\text{max\_keep}\) among all \(\text{dp}[i]\), and subtract \(\text{max\_keep}\) from the total fee to obtain the minimum removal fee.

Complexity

• Time complexity: \(O(N^2)\)
  • The outer loop runs \(N\) times and the inner loop runs up to \(N\) times
• Space complexity: \(O(N)\)
  • The DP array has size \(N\)

Implementation Notes

• Precompute the total sum of all fees

• For DP initialization, the initial value at each position is the fee of that book alone (a subsequence consisting of only \(C[i]\))

• In the inner loop, only process cases where \(A[j] < A[i]\)

• Don’t forget to handle the case when \(N=0\)

  Source Code

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()

This editorial was generated by deepseekv3.