G - Max Sum Plus Plus
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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, -32768 ≤ 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,000, -32768 ≤ 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.
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 -1 4 -2 3 -2 3
Sample Output
6
8
Hint
Huge input, scanf and dynamic programming is recommended.
求最大m字串和，是杭电1003的加强版，个人感觉难度大多了，光看别人博客就看了好几个小时，才看明白什么意思。写的过程中还是碰到了麻烦，ac不了，最后只能无奈得仿照别人写了一遍。打算等以后能力再强一些的时候再回来看看。
因为n非常大为1000000，所以常规方法肯定不行，采用滚动数组节约内存。状态转移方程为now[j]=max(now[j-1],pre[j-1])+num[j];
其中now记载当前状态，pre记载之前的状态。pre[j]用于求num[j+1]时使用。
对于第j个数，令j一定被选中作为加法中的一个因子，now[j-1]+num[j]表示num[j]与前一个数共同组成一串，pre[j-1]+num[j]表示num[j]另起一串,那么now[j]就能够表示当前的最大值了。整个算法的时间复杂度为O(m*n);
在对now[j+1]做这样的处理后，再更新pre[j]的值。
虽然花了我好几个小时，可是还是感觉只是懵懵懂懂的理解，下面贴两篇代码，前一篇是我没有ac的，后一篇是参考别人的。当然细说起来两篇都是参考的，咱就不深究了哈哈。。。
能力还是不行，差远了，只能更努力的去加油，再加油
不过说起来也真弱，第一篇连样例都没过，可是就是想不明白，脑子啊。。。
以下是错误代码：
#include<stdio.h>
#include<string.h>
long num[1000005],pre[1000005],now[1000005];
int max(long a,long b)
{
return a>b?a:b;
}
#define INF 200000000
int main()
{
long m,n,i,j,k,l,s,mm;
while(scanf("%ld%ld",&m,&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%ld",&num[i]);
memset(pre,0,sizeof(pre));
memset(now,0,sizeof(now));
for(i=1;i<=m;i++)
{
for(j=i;j<=n;j++)
{
now[j]=max(now[j-1],pre[j-1])+num[j];
pre[j-1]=now[j-1];
}
}
for(i=1,s=0;i<=n;i++)
if(now[i]>s)
s=now[i];
printf("%ld
",s);
}
return 0;
}
以下是正确的：
#include<stdio.h> #include<string.h> long num[1000005],pre[1000005],now[1000005]; int max(long a,long b) { return a>b?a:b; } #define INF 200000000 int main() { long m,n,i,j,k,l,s,mm; while(scanf("%ld%ld",&m,&n)!=EOF) { for(i=1;i<=n;i++) scanf("%ld",&num[i]); memset(pre,0,sizeof(pre)); memset(now,0,sizeof(now)); for(i=1;i<=m;i++) { mm=-INF; for(j=i;j<=n;j++) { now[j]=max(now[j-1],pre[j-1])+num[j]; pre[j-1]=mm; if(now[j]>mm) mm=now[j]; } } printf("%ld ",mm); } return 0; }