Max Sum Plus Plus
原题链接:https://vjudge.net/contest/165707#problem/A
问题描述
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.
题意
【问题描述】—-最大M子段和问题
给定由 n个整数(可能为负整数)组成的序列a1,a2,a3,……,an,以及一个正整数 m,要求确定序列 a1,a2,a3,……,an的 m个不相交子段,
使这m个子段的总和达到最大,求出最大和。
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 3 1 2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6
8
题解
这里因为是最大问题,很容易联想到是dp做法。但是要怎么写状态转移方程呢?
首先,我们可以发现,对于一个子问题而言,在j个数里面选i个字段做为最优解就可以了,那么细化到最后就是只有一个数,选一个字段,那对于下一状态来说,就是j+1这个数,是并入到j-1里面,还是独立一个字段的问题。所以状态转移方程为dp[i][j]=max(dp[i-1][t],dp[i][j-1])+a[j]; 其中(1<=t<=j-1),所以接下来我们要做的就是怎么去实现这个方程。
由于方程里的dp[i-1][t]数组,如果每次都要重新找一次,那么时间复杂度就是O(mn²)远远超出了时间限制,因此我们需要优化。
①优化时间
在这里,我们可以发现,每个位置的dp[i-1][t]都是从它上一位置维护出来的,因此我们只需要用一个一维数组——maxn[]去维护这个dp[i-1][t],其中maxn[j-1]就是表示j位的dp[i-1][t],因此方程变成了dp[i][j]=max(maxn[j-1],dp[i][j-1])+a[j];
②优化空间
我们知道了j的范围(即n)是1e6,可是没有给i(即m)的范围,因此,如果m超过了100,我们的dp[][]就会爆内存了,所以我们需要优化空间。
在这里,手动模拟一遍,我们可以发现对于每一个dp[i][j],它的dp[i][j-1]要么就是dp[i-1][t],要么就是前i个数全部选择了,然后从i+1一直到j-1连续了过来。为什么是i?因为在第i层,我们需要构造i个字段,那么dp[][]这个数组也不需要存在了,直接用一个临时变量tmp就可以替换了。tmp表示dp[i][j-1],所以现在的方程变成了*tmp=max(maxn[j-1],tmp)+a[j];
代码里面最难理解的就是maxn这个数组怎么维护了,接下来可以边看我代码边看这边的解释,看多几遍估计就能理解了。(PS: maxn数组与代码中的dp数组是同一个数组,而代码里我的下标是从0开始的,所以读者可以自行缩减一位,当然这里有个坑,容我迟点再说)
因为对于maxn这个数组来说,maxn[n]是永远不会用到的,因此它可以用来做临时储存变量。
那么对每一层的maxn来说,它是用来维护下一层的tmp的,然后tmp又会用来维护它自己那层的maxn,所以我们是先用了maxn当前的值维护tmp,再用把这个maxn变成新的维护好的值。所以这里maxn[n]的作用就体现出来了,对j-1来说,它通过一次维护,可以得到一个新的maxn[j-1],然而当前的maxn[j-1]对这层的j是有用的,因此我们把新的maxn[j-1]先暂时存放到maxn[n]里面,然后再在tmp在第j位用完了旧的maxn[j-1](上一层维护出来的)后,再把maxn[n]赋给maxn[j-1],为下一层做准备。
代码
|
|
|
|
|
|
|
写在最后
这里面我wa了好几次,最后在认真模拟后找到了原因,因为我的下标是从0开始的,那么对于只有一个字段的时候来说,初始的tmp是要把第一个数加进去的然而我并没有加,导致了最后一直wa。