点击打开杭电1024
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 S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, ⑶2768 ≤ Sx ≤ 32767). We define
a function sum(i, j) = Si + ... + Sj (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(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im,
jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx 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(ix, jx)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.
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 ⑴ 4 ⑵ 3 ⑵ 3
Sample Output
思路：
经典的动态计划优化的问题：设f(i, j)表示前i个数划分成j段，且包括第i个数的最大m子段和，那末有dp方程：
f(i, j) = max { f(i - 1, j) + v[i], max {f(k, j - 1) + v[i]}(k = j - 1 ... i - 1) } 。可以引入1个辅助数组来优化转移。设g(i, j)表示前i个数划分成j段的最大子段和（注意第i个数未必在j段里面），那末递推关系以下： g(i, j) = max{g(i - 1, j), f(i, j)}， 分是不是加入第i个数来转移 这样f的递推关系就变成： f(i, j) = max{f(i - 1, j), g(i - 1, j - 1)}
+ v[i]，这样最后的结果就是g[n][m]，通过引入辅助数组奇妙的优化了转移。实现的时候可以用1维数组，速度很快 g[i][j]要末和g[i⑴][j]相等，要末和f[i][j]相等 ，f[i][j]-a[i]要末和g[i⑴][j⑴]相等，要末和f[i⑴][j]相等 。转成1维数组 到第i行时：f[j]=max{ f[j],g[j⑴] }+a[i] } g[j]=max{ g[j],f[j] }。
代码实现：
import java.util.*;
class Main{
public static void main(String[] args){
int j;
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int m=sc.nextInt();int n=sc.nextInt();
int[] a=new int[n+1];int[] dp=new int[m+1];int[] dp2=new int[m+1];
for(int i=1;i<=n;i++){
a[i]=sc.nextInt();
}
dp[1]=a[1];dp2[1]=a[1];
for(int i=2;i<=n;i++){
for(j=1;j<=Math.min(i, m);j++){
dp2[j]=Math.max(dp2[j]+a[i], dp[j⑴]+a[i]);
dp[j⑴]=Math.max(dp[j⑴], dp2[j⑴]);
}
dp[j⑴]=Math.max(dp[j⑴], dp2[j⑴]);
}
System.out.println(dp[m]);
}
}
}