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

Автор cooldown, 10 лет назад, По-английски

I am a bit confuse about this problem. I am not sure I understand the dp process correctly.

I define the state as dp[i][j], which means the max sums until the i-th position and j pairs. so,

dp[i][j] will update dp[i+m][j+1] (including numbers starting from i+1 to i+1+m)

dp[i+m+1][j+1](including numbers starting from i+2 to i+2+m)

....

But this solution exceed the time limit. I can't find where is the problem. could you please help me. thank you in advance.

here is my solution, link: http://codeforces.net/contest/467/submission/9970270

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

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Your solution runs in approx. n*n*k operations, which exceeds time limit.

The expected solution runs in n*k.

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

    thanks, but according to my state transform process, I can't make it in n*k. Maybe the dp process I use is wrong, but i don't know why? I read others' codes and find that they use the same define of dp[i][j] as me, but they don't transform the state as i do. My brain stops......