Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 39886 Accepted Submission(s): 14338
Problem Description
Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence $S_1, S_2, S_3, S_4 … S_x, … S_n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S_x ≤ 32767)$. We define a function $sum(i, j) = S_i + … + S_j (1 ≤ i ≤ j ≤ n)$.
Now given an integer $m (m > 0)$, your task is to find m pairs of i and j which make $sum(i_1, j_1) + sum(i_2, j_2) + sum(i_3, j_3) + … + sum(i_m, j_m)$ maximal ($i_x ≤ i_y ≤ j_x$ or $i_x≤ j_y ≤ j_x$ is not allowed).
But I`m lazy, I don’t want to write a special-judge module, so you don’t have to output m pairs of $i$ and $j$, just output the maximal summation of $sum(i_x, j_x)(1 ≤ x ≤ m)$ instead.
Input
Each test case will begin with two integers $m$ and $n$, followed by $n$ integers $S_1, S_2, S_3 … S_n$.
Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 | 1 3 1 2 3 |
Sample Output
1 | 6 |
题意
将一个长度为$n$的数组分成不相交的$m$段,求这$m$段的和的最大值
思路
状态:$dp[i][j]$表示在前$j$个数中取出$i$段的最大和
状态转移方程:$dp[i][j]=max(dp[i-1][k],dp[i][j-1])+num[j] (i-1\leq k \leq j-1)$
由于$m$范围未知,$n\leq 10^6$,所以二维的dp方程无论是在时间上还是在空间上都是不允许的。
那么我们就需要对这个方程进行优化:
不难发现当前状态只与两个状态有关:
- 第$j$个数和前$j-1$个数在一段里
- 第$j$个数和前$j-1$个数不在一段里。
根据这一点,我们把状态降成一维的数组,$dp[j]$表示前$j$个数分$i$段时的最大和,然后用$sum[j-1]$来表示状态一的前$j-1$个数在前$i-1$段的最大和,$dp[j-1]$表示状态二的前$j-1$个数在前$i$段的最大和。
当前状态的转移方程为:$dp[j]=max(dp[j-1],sum[j-1])+num[j]$,持续更新dp与sum数组的值
AC代码
1 |
|