ProblemAsker's blog

By ProblemAsker, 7 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution not correct on this testcase

    9 9
    
    9 6 9 2 7 6 7 1 9
    

    Code output: 7

    Correct output: 6