Problem with DP

Правка en2, от kambingjantan, 2015-12-12 20:20:45

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 [1, i - 1]. And then fill the table with DP[i, j] = max{DP[k, i - 1]} + 1 if only Sumk, i - 1 ≤ Sumi, j

Are there any flaws with my approach?

Теги dynamic programming, acm icpc regional, partition

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский kambingjantan 2015-12-12 20:23:06 8 Tiny change: ' covers $[1, i - 1]$. And th' -> ' covers $[i, j]$. And th'
en3 Английский 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 Английский kambingjantan 2015-12-12 20:20:45 2 Tiny change: ' [problem C](https://' -> ' [problem G](https://'
en1 Английский kambingjantan 2015-12-12 20:18:36 689 Initial revision (published)