点击打开杭电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,⑶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. ^_^
Given a consecutive number sequence S1,S2,S3,S4 ... Sx,... Sn (1 ≤ x ≤ n ≤ 1,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,S3 ... Sn.
Process to the end of file.
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
6 8
思路：
经典的动态计划优化的问题：设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,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]);
}
}
}
