kambingjantan's blog

Problem with DP
By kambingjantan, history, 9 years ago, In English

Hi guys. I just tried to solve the recent ICPC Singapore problem G with DP bottom up. The summary of description is like this :

Given sequence with length N < 3000 with each in range 1 and 109. Find the maximum partition can be made with each sum of partition elements cannot bigger than sum of elements on the right partition

My answer is by make table DP[i, j] contains maximum partition can be made from element [1, j] with last partition covers [i, j]. And then fill the table with DP[i, j] = max{DP[k, i - 1]} + 1 if only Sumk, i - 1 ≤ Sumi, j

My solution

Are there any flaws with my approach?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

int -> long long

Initialize dpp to  - ∞. With dpp=0 you might be considering partitions of some subarray of the original array, like [2..3], [4..5] for the subarray [2..5], when you really have to partition the whole array.

Counter test:

4
1000 1 2 3
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry, but can you explain a bit why dpp=0 is wrong? I still dont understand

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      If you can't find some valid partition ending at i - 1, you are simply considering you can start a new partition from i, ignoring all previous elements. For example, in the countertest above you are ignoring briefcase 1 in your optimal solution, when you have to use it. That's because your default value of dpp=0 and dp[2][_] will be 0 (1-indexed), which is not correct, since there's no valid partition to it's left. Then when you get to dp[3][], you will make a invalid 1-partition using previous value of dp[2][].

      → Reply