Need help with a problem from VOI 2005

Правка en1, от xuanquang1999, 2016-02-14 18:26:32

I'm trying to solve the following problem (from VOI 2005).

Given a sequence a with n numbers, find the minimum M such that there's a way to split sequence a into k non-empty continuous subsequence and the total sum of each subsequence does not exceed M.

Constrains: 1 <= k <= n <= 15000, |ai| <= 30000, ai may be negative.

The best solution I can come up for this problem is the following O(n^2*k) DP solution:

Call f[i][k] the minimum value M for the sequence that contain first i numbers, d[i] the sum of the first i number of sequence. Then we have the following formula: f[i][k] = min(max(f[j][k], d[i]-d[j])) (with 0 <= j < i)

Of course, with such big constrains, this solution is not fast enough. Is there a faster solution for this? Thanks in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский xuanquang1999 2016-02-15 06:09:59 2 Tiny change: 'max(f[j][k], d[i]-d[' -> 'max(f[j][k-1], d[i]-d['
en2 Английский xuanquang1999 2016-02-14 18:27:26 10
en1 Английский xuanquang1999 2016-02-14 18:26:32 831 Initial revision (published)