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

Автор kambingjantan, история, 9 лет назад, По-английски

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?

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

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

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
  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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][].