Блог пользователя ProblemAsker

Автор ProblemAsker, 3 года назад, По-английски

Input: array A[] of length N (1<=N<=400) , K (1<=K<=400)

In one move : you can remove any subarray size at most K which all element in it are the same

Question: Find minimum number of moves to make array empty.

It’s from my past OI problem and editorial said it use Matrix Chain Multiplication DP, but I can’t come up with it.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I would like to know as well, and can't think of sol currently.

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

I'll describe an $$$O(n^3)$$$ dp solution. Let $$$dp[l][r]$$$ denote the answer for the range $$$[l..r]$$$. First, try splitting the current range into two. Set $$$dp[l][r]$$$ to be the min of all $$$dp[l][i]+dp[i+1][r]$$$ where $$$l \leq i < r$$$. Second, consider doing the operation on some prefix and suffix of the range (and using other dp values to get the answer for the middle). You need to choose some prefix and suffix s.t. all values are the same and the total length is $$$\leq k$$$. Brute force the length of the prefix to remove. Given some prefix to remove, you would want to remove the largest suffix that you can (because adding elements to the array can only increase the answer). You can easily calculate what is the largest suffix you can take (with a bit of precomp). There are $$$O(n^2)$$$ states, and each transition is $$$O(n)$$$, leading to a final time complexity of $$$O(n^3)$$$ and memory complexity of $$$O(n^2)$$$. The answer to the problem is $$$dp[0][n-1]$$$. See my code for more details.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your solution not correct on this testcase

    9 9
    
    9 6 9 2 7 6 7 1 9
    

    Code output: 7

    Correct output: 6