avinash007's blog

Range Dp

By avinash007, history, 4 years ago, In English

You are given N marbles in different colors. You have to remove marbles till there are no marbles left. Each time you can choose continuous marbles with the same color, remove them and get k*k points. Find the maximum points you can get.

1 ≤ N ≤ 100 0 ≤ Ai ≤ 100

INPUT 6 4 3 1 1 4 2 OUTPUT 10

Remove 1, then 3, then 4 and 2, we get 2*2+1*1+2*2+1*1 = 10

Please provide link to similar Problems.

Also I would like to know your dp states and Transitions

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link the problem ?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

Keep dp[i][j] as being the maximum score of the interval [i, j). For each of these intervals, look at the first element a[i]. You can either just do 1 + dp[i+1][j] or combine multiple occurrences of a[i] in this interval. Say these indices are t1, t2, t3, .... then for all prefixes of this sequence, you can update dp[i][j] with dp[t1+1][t2] + dp[t2+1][t3] + ... + dp[tk+1][j] + k*k. So you can just iterate for all possible k and get the max of them. You can check out the code here: code

EDIT: If you want a similar-style problem, I remember a classic one from the AtCoder DP contest N — Slimes

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

    Thanks

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It gets wrong answer on this test case.

    8
1 2 2 1 2 2 1 1

    The prefixes need not be continuous for optimal score. Here, if we consider range [0,7], leaving the second 1 at index 3 is best for optimal score (26) compared to taking it (score : 24)

    You can test solution here.

    https://leetcode.com/problems/remove-boxes/description/

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yep, you are right :) i think i didn't see that at the time. thanks so much for pointing it out, though!

      → Reply