杭电1024（Max Sum Plus Plus）

发布时间：2020-12-13 20:46:38 所属栏目：PHP教程来源：网络整理

导读：点击打开杭电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 con

点击打开杭电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 S₁,S₂,S₃,S₄ ... S_x,... S_n (1 ≤ x ≤ n ≤ 1,000,⑶2768 ≤ 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₁,j₁) + sum(i₂,j₂) + sum(i₃,j₃) + ... + 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₁,S₃ ... 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 ⑴ 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]); } } }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!