杭電1024（Max Sum Plus Plus）
來源：程序員人生 發布時間：2015-08-08 08:45:35 閱讀次數：2488次
點擊打開杭電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]);
}
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
