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://mirror.codeforces.com/contest/467/submission/9970270
Your solution runs in approx. n*n*k operations, which exceeds time limit.
The expected solution runs in n*k.
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......