最大连续子序列和.pptx

《最大连续子序列和.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、关于最长连续子序列的和的运用1、首先引入最长连续子序列和的概念1给定一串序列a1,a2,a3,a4……an,求从i到j的一段连续序列，使得序列相加得到和最大。其中1<=i<=j<=n.如果所有整数为负,最大值为0(空子序列值为0)算法1O(n*n)枚举左右边界，，大概代码是这样子的。fori:=1tondoforj:=Itondobeginifsum[I,j]>maxthenmax:=sum[I,j]end;其中sum数组表示从i到j这段连续子序列的和是可以预处理出来的。应该不需要解释把。算法2o(

2、n)直接上代码吧。。这个自己体会下吧。有点类似于单调队列的思想。很容易想通的。fori:=1tondobegins:=s+a[i];ifs<0thens:=0;ifs>maxthenmax:=s;end;当然这一切的前提都是建立在子序列的和要大于等于0的情况下的。上题目！三．最大子序列题目描述：上次数学考试考了一道这样的题目：一个有n个整数的数字序列，其间有正负整数，现在的任务是求出两段不相交的连续子序列，使这两段中的数字和最大。输入数据：第一行，一个数n，表示整数的个数。第二行n个数，描述这个序列

3、。输出数据：仅一行，表示最大的数字和。输入样例：1012-3214-3212（取子序列2，1，4和2，1，2，得到最大的和）输出样例：12数据约定：对于50%的数据，n<=100；对于70%的数据，n<=1000；对于100%的数据，n<=1000000这题目很简单就是最长连续自序列的变形。求两端嘛。。正向做一次反向做一次枚举中间分割线。大概代码如下求出正向f1数组，f1[i]表示从第一个到第i个最大连续子序列和。求出反向f2数组，f2[i]表示从倒数第一个到第i个最大连续子序列和。fori:=1t

4、ondoans:=max(ans,f1[i]+f2[i+1]);描述Description黄金矿工是一个经典的小游戏，它可以锻炼人的反应能力。该游戏中，可以通过“挖矿”获得积分并不断升级。玩家可以在线玩flash版黄金矿工，也可以下载后玩单机版黄金矿工。目前，黄金矿工小游戏有多个版本，例如黄金矿工双人版，黄金矿工单人版等。Jimmy是一位黄金矿工，他所在的金矿是一个n*n的矩形区域（俯视），区域内有黄金、石头和TNT，由一个n*n的矩阵描述。黄金的价值对应矩阵中的正值，石头的价值对应矩阵中的负值，T

5、NT由0表示。换句话说，挖到黄金赚钱，石头亏损，如果挖到TNT就挂了~_~Jimmy租到的挖矿工具很特别，它的形状是一个长宽任意（均为正整数）的矩形，可以取走被该工具覆盖的矩形区域内的所有物品，但如果该区域内有TNT，该工具将被炸毁，此时Jimmy将不得不赔偿矿主+∞元！！！需要注意的是，该工具只能在金矿范围内使用（即不得超出金矿边界），且租金为每次使用十元。现在，Jimmy想知道，如果他至多只有一次租用该工具的机会，他能获得的最大收益是多少。当然，如果Jimmy租用该工具无论如何都会亏损，他可

6、以不租用，此时收益为0.输入格式InputFormat第一行：一个整数n接下来n行，每行n个整数（绝对值<100），为题目中所描述的矩阵。输出格式OutputFormat一个数，即Jimmy所能获得的最大收益。Exampleinput30-1-10-120-1900Exampleoutput0[说明]此题中出现的所有数全为整数[背景]SubRaY有一天得到一块西瓜,是长方体形的....[题目描述]SubRaY发现这块西瓜长m厘米,宽n厘米,高h厘米.他发现如果把这块西瓜平均地分成m*n*h块1立方

7、厘米的小正方体,那么每一小块都会有一个营养值(可能为负,因为西瓜是有可能坏掉的,但是绝对值不超过200).现在SubRaY决定从这m*n*h立方厘米的西瓜中切出mm*nn*hh立方厘米的一块小西瓜(一定是立方体形,长宽高均为整数),然后吃掉它.他想知道他最多能获得多少营养值.(0<=mm<=m,0<=nn<=n,0<=hh<=h.mm,nn,hh的值由您来决定).换句话说,我们希望从一个m*n*h的三维矩阵中,找出一个三维子矩阵,这个子矩阵的权和最大.eatwatermelon一个2*3*4的例子,

8、最优方案为切红色2*3*1部分[数据范围]对于30%的数据,h=1,1<=m,n<=10对于全部的数据,1<=h<=32,1<=m,n<=50,保证h<=m,n输入格式首行三个数h,m,n(注意顺序),分别表示西瓜的高,长,宽.以下h部分,每部分是一个m*n的矩阵,第i部分第j行的第k个数表示西瓜第i层,第j行第k列的那块1立方厘米的小正方体的营养值.输出格式SubRaY所能得到的最大营养值Exampleinput234412805-48430192149101731