Problem with DP

Revision en4, by kambingjantan, 2015-12-12 20:23:06

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?

Tags dynamic programming, acm icpc regional, partition

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English kambingjantan 2015-12-12 20:23:06 8 Tiny change: ' covers $[1, i - 1]$. And th' -> ' covers $[i, j]$. And th'
en3 English kambingjantan 2015-12-12 20:21:46 43 Tiny change: 'i, j}$\n\nAre th' -> 'i, j}$\n\n[My solution](http://ideone.com/OdxY57)\n\nAre th'
en2 English kambingjantan 2015-12-12 20:20:45 2 Tiny change: ' [problem C](https://' -> ' [problem G](https://'
en1 English kambingjantan 2015-12-12 20:18:36 689 Initial revision (published)