Max Sum Plus Plus

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, -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.

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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
Max Sum Plus Plus
Problem DescriptionnNow 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.nnGiven 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).nnNow 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).nnBut 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. ^_^n nnInputnEach test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.nProcess to the end of file.n nnOutputnOutput the maximal summation described above in one line.n nnSample Inputn1 3 1 2 3n2 6 -1 4 -2 3 -2 3n nnSample Outputn6n8
Max Sum Plus Plus问题???
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.rnrnGiven 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).rnrnNow 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).rnrnBut 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. ^_^rnrn rnrnInputrnEach test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.rnProcess to the end of file.rnrn rnrnOutputrnOutput the maximal summation described above in one line.rnrn rnrnSample Inputrn1 3 1 2 3rn2 6 -1 4 -2 3 -2 3rn rnrnSample Outputrn6rn8rnrnrn第二组输出的8是哪两组sum相加得到的???sum(1,2)和sum(2,6)可以吗?但结果是9
Max Sum Plus Plus(ACM ,c语言)
int main() { int i,j,m,n,t,p,q,k; while(scanf("%d %d",&m,&n)==2) { for(k=0;k<n;k++) { scanf("%d",&a[k]); }
hdu1024 Max Sum Plus Plus(最大子段和加强版)
关键字:dp   滚动数组 题意:输入n,m表示 一排n个数,求m个不相交的子段,他们和最大。 思路:果断dp啊,最大子段和的变形,联想最大子段和的dp[i] 设以当前i为结尾的子段和最大的结果,这里设dp[i][j]为以j结尾构成了i段不相交子段和的最大结果。 我们就要思考当前dp[i][j]是由那些状态转移过来?思考这里对于每个数字,我们的策略是要么选择他作为当前这段的,要么让它单独
MAX + plus
EDA编程软件,版本简洁好用,是一个不错的编程软件。
HDU 1024Max Sum Plus Plus
代码是别人的博客上找的链接是http://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.htmlrn[code=c]rn#includern#includern#includernusing namespace std;rn#define MAXN 1000000rn#define INF 0x7fffffffrnint dp[MAXN+10];rnint mmax[MAXN+10];rnint a[MAXN+10];rnint main()rnrn int n,m;rn int i,j,mmmax;rn while(scanf("%d%d",&m,&n)!=EOF)rn rn for(i=1;i<=n;i++)rn rn scanf("%d",&a[i]);rn mmax[i]=0;rn dp[i]=0;rn rn dp[0]=0;rn mmax[0]=0; rn for(i=1;i<=m;i++)rn rn mmmax=-INF;rn for(j=i;j<=n;j++)rn rn dp[j]=max(dp[j-1]+a[j],mmax[j-1]+a[j]);//不明白dp数组和mmax数组的作用,可以说下这段代码的意思么rn mmax[j-1]=mmmax;rn mmmax=max(mmmax,dp[j]);rn rn rn printf("%d\n",mmmax); rn rn rn return 0; rn rnrnrnrn[/code]
HDU1024 Max Sum Plus Plus(DP动态规划 最大子串和增强版)
Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 20708    Accepted Submission(s): 6886 Problem Description Now I t
HDU - 1024 Max Sum Plus Plus (多段最大连续和+状态压缩)
Max Sum Plus Plus HDU - 1024 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
hdu1024 Max Sum Plus Plus(M段子序列的最大和)
会做一段子序列的最大和,但没想到M段子序列的最大和这么难,完全不会啊! 看了题解几乎清一色都是这种做法,方法和一段子序列的思路完全不一样啊。。。 dp[j]表示以第j个元素结尾的i个子段的最大和,包含a[j]。 pre[j]表示第j个元素以前元素的i个子段的最大和,不包含a[j]。 temp用于存放临时最大值。 真的很不好凭空理解,只好写下来了。 可以看出,当前
hdu 1024Max Sum Plus Plus
Problem DescriptionNow I think you have got an AC in Ignatius.Ls "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more di
基础DP A - Max Sum Plus Plus (有趣的递推)
A - Max Sum Plus Plus 题目链接 ps:感觉这是暑假集训到现在遇到的最变态最难理解的题目了。。。刚刚接触动态规划,实在不懂怎么写,就看了大佬的题解。 本题参考博文:https://blog.csdn.net/lishuhuakai/article/details/8067474 题意: 给出一个有n个数字的序列,要求从序列中取出m个段,数字可以不全部使用。要求所有段...
MAX PLUS使用说明
MAX PLUS2 的详细使用说明,对于想学习可编程逻辑器件的学者是不可多得的好资料。
MAX PLUSⅡ 的快速入门
最近做毕业设计搜集的资料,感觉很有用,所以共享,希望对大家有所帮助!
max plus II 证书
有证书才能用这是我从官网上费了好大劲下来的
MAX PLUS ii破解软件
MAX PLUS ii破解软件
max plus许可证
max plus许可证
max plus软件应用
max plus软件相关应用,比较详细。试验箱的使用方法等系列讲解。比较受用 适合学生学习 仅供参考
MAX PLUS II 入门指南
EDA编程软件 可以仿真波形的MAX PLUS II 入门,如何建文件,编程,仿真等
max plus ii 入门指导
适合新手入门使用!有利于快速掌握使用max plus ii!
ATCODER:Or Plus Max(二进制递推)
E - Or Plus MaxTime limit : 2sec / Memory limit : 1024MBScore : 700 pointsProblem StatementThere is an integer sequence of length 2N: A0,A1,…,A2N−1. (Note that the sequence is 0-indexed.)For every int...
MAX PLUS II入门指南
1、 2、 按步骤安装即可 3、注册:开始——所有程序——MAX PLUS II BASELINE——OPTIONS—— LICENSE SETUP 找到注册文件所在路径OK即可
MAX十PLUSⅡ操作指南
MAX+PLUSⅡ是美国Altera公司开发的一种全集成化的可编程逻辑设计软件平台。具有丰富的图形界面和完整、可即时访问的在线文档。提供一个真正与结构无关的可编程逻辑设计环境; 全集成化的一套可编程逻辑开发工具; 提供多种输入方式;可方便与其它工业标准设计输入、综合与校验工具链接。
☆HDU 1024 Max Sum Plus Plus 绝对能看懂得题解(难题,多个子段和的和最大)
这题真的是不会做,看题解也看了好久,看网上题解,感觉他们解释的一点也不清楚,好像只是照着kuangbin的代码瞎讲讲,有些细节跟技巧都没说,我自己感觉不知道那些自己写代码肯定写不出来
【HDU 1024】Max Sum Plus Plus(DP+滚动数组优化+最大m段字段之和)
DescriptionNow 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 probl
HDU 1024
New~ 欢迎“热爱编程”的高考少年——报考杭州电子科技大学计算机学院  关于2015年杭电ACM暑期集训队的选拔  Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1951
kuangbin求带飞DP1 Max Sum Plus Plus(动态规划+滚动数组)
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
HDU-1024 Max Sum Plus Plus(M段连续子段和+dp图表规律优化)
Now I think you have got an AC in Ignatius.L's &quot;Max Sum&quot; problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem. ...
HDU1024 Max Sum Plus Plus(滚动数组优化空间+dp空间换时间)
题意 输入n个数。选取m个不重叠的区间,使得m个区间内的数之和最大。 解题 要记录两个量:选取了的数的个数、选取的区间个数。故设dp[i][j]表示选取了i个不重叠区间、选取了j个数、最后一个区间包含第j个数的选取方式的值。 这样,dp[i][j]={dp[i][j-1],dp[i-1][k]}+s[j],k取值范围是[i-1,j-1]。 空间复杂度为O(n*m),时间复杂度为O(n*m...
HDU 1024 Max Sum Plus Plus (若干子区间求解最大值)
思路:对于此类型的题目,可以从以下几个方面分析,    1.以当前的数为切入点,只有两种情况(1)当前的数单独的新放到一个区间.(2)将其放入和j-1同个区间。那么我们可以用dp[i][j]表示在前j个数划分了i个区间。固有状态转移方程:dp[i][j]=max(dp[i-1][j-1],dp[i][j-1])+a[j];由于m的范围没有给出所以不可开dp[m][n]的数组。那么就需要有优化的方
HDU 1024 Max Sum Plus Plus(动态规划 很详很详解)
先来题 Max Sum Plus PlusNow 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 diffi
HDU1024 Max Sum Plus Plus (基础dp n个数求m个不相交子段和的最大值)
题目的大意是酱紫:       输入两个数,m和n ,意思是n个数求m个不相交的(重读)子段,输出子段和的最大值。 举一个栗子: 2 6 // 6个数 2个不相交子段 -1 4 -2 3 -2 3        输出结果为 8    两个子段为{4},{3,-2,3};(当然这只是最大值其中一种,还可以是{4,3},{-2,3}等等...
Max Sum Plus Plus HDU - 1024 (滚动数组优化dp+构造dp状态转移方程)
传送门 题意:找出k段不相交的子序列,使得和达到最大 题解:参考了传送门 这道题使用dp,设w[i][k]为在k个元素下选定了i段,并且一定选了k这个元素的最大值,设b[i][k]为在k个元素下选定了i段,并且不一定选了k这个元素,最后看下dp状态转移方程: w[i][k]=max(b[i-1][k-1],w[i][k-1])+a[k] b[i][k]=max(b[i][k-1],w[i...
HDU 1024 Max Sum Plus Plus(求m个不相交连续子序列最大和/01背包)
题目链接: HDU 1024 Max Sum Plus Plus 题意: n个数,求m个不相交连续子序列的最大和。n<=1e6,单个数[-32768,32767],m>0. 分析: dp[i][j][1]表示在求前i个数的j个不相交的最大子序列和时不要第i个数 dp[i][j][0]表示要第i个数。 *初始化:* dp为-INF,但是dp[0][0][0]=dp[0][0][1]=0
Notepad plus plus
非常好用的文本编辑工具,用来写代码很方便
plus
plus
notepad++ notepad plus plus
notepad++ 下载后把后缀修改成exe 运行安装即可!
C plus plus today
C plus plus today, 简短的C++ 发展
Cengage - C Plus Plus
Cengage - C Plus Plus Programming From Problem Analysis To Program Design 6th Edition 2013
c plus plus手册
c++手册,c++库函数、stl库函数查询。
c plus plus primer
适合c++学习,尤其是对于初学者,对于C++高手来说也可以起到一定的补充作用
相关热词 c# 标准差 计算 c#siki第五季 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池