To solve this problem, we need to find the maximum number of elements that can be removed from a list such that the remaining elements form a sequence where each element is divisible by the previous one. This problem can be reduced to finding the length of the longest divisible subsequence (LDS) and then subtracting this length from the total number of elements in the list.
Approach
- Dynamic Programming (DP) Setup: We use a DP array where
dp[i]represents the length of the longest divisible subsequence ending at indexi. - DP Transition: For each element at index
i, check all previous elements (from index0toi-1). If the current element is divisible by the previous element, updatedp[i]to be the maximum of its current value ordp[j] + 1(wherejis the index of the previous element). - Calculate Result: The length of the longest divisible subsequence is the maximum value in the DP array. The maximum number of elements to remove is the total number of elements minus this length.
Solution Code
arr = list(map(int, input().split()))
n = len(arr)
if n == 0:
print(0)
else:
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[i] % arr[j] == 0:
dp[i] = max(dp[i], dp[j] + 1)
max_len = max(dp)
print(n - max_len)
Explanation
- Dynamic Programming Array: The DP array
dpis initialized to1because each element itself is a subsequence of length1. - Transition Logic: For each element, we check all previous elements to see if the current element is divisible by them. If so, we update the DP value for the current element to reflect the longest subsequence ending at that element.
- Result Calculation: The maximum value in the DP array gives the length of the longest divisible subsequence. Subtracting this from the total number of elements gives the maximum number of elements that can be removed.
For the input 1 2 3 4 5 6 7 8 9 10, the longest divisible subsequence is 1 → 2 → 4 → 8 (length 4). Thus, the maximum number of elements to remove is 10 - 4 = 6.
Output: 6


作者声明:本文包含人工智能生成内容。