撰写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 ≤ iy ≤ 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. ^_^
InputEach test case will begin with two integers m and n, followed by n integers S 1, S2, S 3 … S n.
Process to the end of file.
OutputOutput 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
Hint
Huge input, scanf and dynamic programming is recommended.
- 题意
- 给n个数，求m个不重叠片段的最大值。
- 题解
- 这题明显有两个状态，一个是n，一个是m
- 类比于背包问题以及这类题目的经验来看，以m作为第一维是比较合适的（阶段），若以n作为第一维，则状态混乱。
- 显然，需要第三维进行递推，所以d[i][j]=max(d[i][j-1]+a[j],d[i-1][k]+a[j]);
- 即a[j]加在i段的末尾 或者 前面有i-1段、k个数，而a[j]自成一段。
- 但是，这样的话，无论是时间复杂度还是空间复杂度，都会BOOM，所以需要优化，
- 我们发现，所谓的第三维k，其实就是选出上一层（i-1）的1~j-1中(更确切地说是i-1~j-1)的最大的dp[j-1],所以只要保存从i-1~j-1的上一段的最大的dp[j-1],则ok，注意，这里需要在使用完成上一段的max[j-1]后再更新这一段的max[j-1],而不影响前这一段max[j-1]。
- 代码：
- 未简化版本：
-
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define rep(i,a,n) for(int i=a;i<=n;i++) const int maxn=1e6+10; const int INF = 0x3f3f3f3f; int a[maxn]; int dp[10][maxn]; int main(){ int n,m; while(scanf("%d%d", &m,&n)==2){ rep(i,1,n)scanf("%d", &a[i]); memset(dp,-INF,sizeof(dp)); for(int i=0;i<=n;i++) { dp[i][0]=0; } rep(i,1,m){ dp[0][i]=0; } int maxx=-INF; rep(i,1,m){ rep(j,i,n){ rep(k,i-1,j-1){ dp[i][j]=max(dp[i][j],max(dp[i][j-1]+a[j],dp[i-1][k]+a[j])); } } } rep(i,m,n){ maxx=max(maxx,dp[m][i]); } printf("%d\n", maxx); } return 0; } - 简化版本：
-
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define rep(i,a,n) for(int i=a;i<=n;i++) const int maxn=1e6+10; const int INF = 0x7fffffff; int a[maxn]; int dp[maxn]; int ma[maxn]; int main(){ int n,m; while(scanf("%d%d", &m,&n)==2){ rep(i,1,n)scanf("%d", &a[i]); for(int i=0;i<=n;i++) { ma[i]=0; dp[i]=0; } int maxx; rep(i,1,m){ maxx=-INF; rep(j,i,n){ dp[j]=max(dp[j-1]+a[j],ma[j-1]+a[j]); if(j!=i)//因为ma[j-1]保存的是 i-1~j-1中的最大值 //但实际上可以省略判断，因为得到多余值之后也不会被用到 ma[j-1]=maxx;//最后的j对应的值不记录，因为原来k的范围就是从i-1~j-1,而每次j的最大值是固定的 maxx=max(maxx,dp[j]);//两个作用，一是保存前一次j的最大值，二是保存最后一次i中的最大值 // ma[j]=maxx;这样做会导致前一次的值被覆盖 } } printf("%d\n", maxx);//最大值在dp[m][m~n]中 } return 0; }