最大连续子段求和相关题目By  huaidan 发表于 2012/6/8 9:43:00 

0

推荐

例题:打水漂

 

题目描述

题目描述：
君不知，打靶大牛goleenuoer可喜欢打水漂了，他的靶子可以打到河面上的任何一条鱼,可是他的水漂打得实在是烂,无论怎么打那石子只会在河面上跳跃两次就“扑通”了.这天他又来打了.这条宽w米,每隔一米都会有一条鱼,每条鱼都有它的美观值.他想知道如何打才能得到两条鱼之间最大的美观值总和.刚接触OI的他想请您来解答,您能帮助他吗???

输入格式

输入文件包含n+1个整数,第一行为一个整数n(n<=10000).从第二行工n个数,第i个整数表示第i条鱼的美观值范(围为-500..500).当所有整数都为负数时输出0.

输出格式

输出文件包含两行,第一行为石子的起点和落点,用空格隔开.第二行为一个整数表示所得到的两条鱼之间美观值总和.

【样例输入】

6

-2  11  -4  13  -5  -2

【样例输出】

2  4

20

【问题分析】此题就是求连续和最大，并且输出起点和终点，

方法1：就是枚举起点，计算结果，在刷新ans的同时把起点head，终点tail送出；

方法2：主要是数学思想，temp保存的是前面连续一段的加和，（思想：一个数 + 大于0的数 > 自己本身），我想你会懂的，我不多说！

两个方法效率绝对不同，2的效率要高的多！

【样例程序1】

program dashuip;

 const maxn=10010;

 var n,head,tail,ans:longint;

     p:boolean;

     a:array[0..maxn] of longint;

 procedure init;

  var i:longint;

   begin

     assign(input,'dashuip.in');reset(input);

     assign(output,'dashuip.out');rewrite(output);

     readln(n);p:=false;

     for i:=1 to n do

       begin

         read(a[i]);

         if  a[i] > 0 then p:=true;

       end;

   end;

 procedure print1;

  begin

write('0');

    close(input);close(output);

  end;

 procedure print2;

  begin

    writeln(head,' ',tail);

write(ans);

    close(input);close(output);

  end;

 procedure main;

  var i,j,l,r,temp:longint;

    begin

      if not p then begin print1;halt;end;

      l:=1;r:=n;

      while a[l] <= 0 do inc(l);

      while a[r] <= 0 do dec(r);

      ans:=-maxint;

      for i:=l to r do

        begin

          temp:=0;

          for j:=i to r do

            begin

              temp:=temp + a[j];

              if temp > ans then begin ans:=temp;head:=i;tail:=j;end;

            end;

        end;

   end;

 begin

  init;

  main;

  print2;

 end.

【样例程序2】

program dashuip;

 const maxn=10010;

 var n,head,tail:integer;

     ans:longint;p:boolean;

     a:array[0..maxn] of integer;

 procedure init;

  var i:integer;

   begin

     assign(input,'dashuip.in');reset(input);

     assign(output,'dashuip.out');rewrite(output);

     readln(n);

     p:=false;

     for i:=1 to n do

       begin

         read(a[i]);

         if a[i] >= 0 then p:=true;

       end;

   end;

 procedure print1;

  begin

   write('0');

   close(input);close(output);

  end;

 procedure print2;

  begin

   writeln(head,' ',tail);

   write(ans);

   close(input);close(output);

  end;

 procedure main;

  var i,l,r,tem:integer;

      temp:longint;

   begin

     if not p then begin print1;halt;end;

     l:=1;r:=n;

     while a[l] <= 0 do inc(l);

     while a[r] <= 0 do dec(r);

     temp:=a[l];ans:=a[l];head:=l;

     for i:=l+1 to r do

       begin

         if temp < 0 then begin temp:=a[i];tem:=i;end

           else temp:=temp + a[i];

         if temp > ans then begin ans:=temp;head:=tem;tail:=i;end;

       end;

   end;

 begin

  init;

  main;

  print2;

 end.

 

例题:奥运火炬到厦门

 

题目描述

背景:5月12日，在厦门人民的热烈欢迎下，象征着和平、友谊、圣洁的奥运火炬终于来到了厦门，开始了传递……
描述：厦门市市长宣布：“要把这次火炬接力办的很有意义。”“有意义”是什么意思呢？厦门市市长别出心裁地给它下了个定义：每个火炬手都有个意义值，可以将他们顺次看作一个首尾相接的环，而整个火炬接力的意义值是这个环的最大和连续子串。
比如： 串是 -2  2  0  1  -48  1，显然其最大和连续子串是2  0  1，其和是3。现在给定n个火炬手的意义值，请算出整个火炬接力的意义值（意义值可能为负数）

输入格式

第1行一个整数n(1<=n<=5000)表示n个火炬手
第2行有n个整数，每个整数都在longint的范围内。

输出格式

火炬接力的意义值。

【样例输入】

2

1  3

【样例输出】

4

【问题分析】注意如何把环剪开，在就是数论知识(一个数+大于0的数)>自身；因为数据少，所以朴素能过；如果数据量大，还是建议应用线段树来处理！样例程序就是朴素的！

【样例程序】

program aoyunhjdxm;

 const maxn=5010;

 var n:integer;

     ans:int64;

     a:array[0..maxn*2] of longint;

 procedure init;

  var i:integer;

   begin

     assign(input,'stdin.in');reset(input);

     assign(output,'stdout.out');rewrite(output);

     readln(n);

     for i:=1 to n do

       begin

         read(a[i]);

         a[n+i]:=a[i];

       end;

   end;

 procedure find(L,R:integer);

  var i:integer;

      max,temp:int64;

   begin

     temp:=a[L];max:=a[L];

     for i:=L+1 to R do

       begin

         if temp > 0 then temp:=temp + a[i] else temp:=a[i];

         if temp > max then max:=temp;

       end;

     if max > ans then ans:=max;

   end;

 procedure main;

  var i:integer;

   begin

     ans:=-maxlongint;

     for i:=1 to n do find(i,n+i-1);

   end;

 procedure print;

  begin

    write(ans);

    close(input);close(output);

  end;

 begin

  init;

  main;

  print;

 end.

 

例题:最大加权矩形

 

题目描述

给定一个正整数n（ n<=100），然后输入一个N*N矩阵。求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于[-127,127]

输入格式

第一行：n，接下来是n行n列的矩阵。

输出格式

最大矩形（子矩阵）的和。

【样例输入】

4

0  -2  -7  0

9  2  -6  2

-4  1  -4  1

-1  8  0  -2

【样例输出】

15

【问题分析】最大子段求和，数据处理是由面压成线！用的时候在释放！

【样例程序】

program zuidajqjx;

 const maxn=110;

 var n:integer;

     ans:longint;

     a:array[0..maxn,0..maxn] of integer;

     s:array[0..maxn] of longint;

 procedure init;

  var i,j:integer;

   begin

     assign(input,'zuidajqjx.in');reset(input);

     assign(output,'zuidajqjx.out');rewrite(output);

     readln(n);

     fillchar(a,sizeof(a),0);

     for i:=1 to n do

       for j:=1 to n do

         read(a[i,j]);

   end;

 procedure main;

  var i,ii,j:integer;

      tem,sum:longint;

   begin

     fillchar(s,sizeof(s),0);

     for i:=1 to n do

       for j:=1 to n do

         inc(a[i,j],a[i-1,j]);

     ans:=-maxlongint;

     for i:=n downto 1 do

       for ii:=0 to i-1 do

         begin

           for j:=1 to n do s[j]:=a[i,j]-a[ii,j];

           tem:=s[1];sum:=s[1];

           for j:=2 to n do

             begin

               if tem > 0 then inc(tem,s[j]) else tem:=s[j];

               if tem > sum then sum:=tem;

             end;

           if sum > ans then ans:=sum;

         end;

   end;

 procedure print;

  begin

    write(ans);

    close(input);close(output);

  end;

 begin

  init;

  main;

  print;

 end.

 

例题：吃西瓜

 

题目描述

[说明]此题中出现的所有数全为整数
[背景]SubRaY有一天得到一块西瓜,是长方体形的....
[题目描述]SubRaY发现这块西瓜长m厘米,宽n厘米,高h厘米.他发现如果把这块西瓜平均地分成m*n*h块1立方厘米的小正方体,那么每一小块都会有一个营养值(可能为负,因为西瓜是有可能坏掉的,但是绝对值不超过200).
现在SubRaY决定从这m*n*h立方厘米的西瓜中切出mm*nn*hh立方厘米的一块小西瓜(一定是立方体形,长宽高均为整数),然后吃掉它.他想知道他最多能获得多少营养值.(0<=mm<=m,0<=nn<=n,0<=hh<=h.mm,nn,hh的值由您来决定).
换句话说,我们希望从一个m*n*h的三维矩阵中,找出一个三维子矩阵,这个子矩阵的权和最大.

一个2*3*4的例子,最优方案为切红色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所能得到的最大营养值

【样例输入】

2  3  4

4  1  2  8

0  5  -48  4

3  0  1  9

2  1  4  9

1  0  1  7

3  1  2  8

【样例输出】

45

【问题分析】说穿了就是最大子段求和，但是如何处理呢？方法很优秀，值得好好学习！由立方体压缩成平面，再由平面压缩成线段，接下来就是最大子段求和！关键就是如何构造这个一维数组，压缩之后在释放出来计算，最后就是如何构造出一个小的立方体，先把i点释放成面，在把面释放成体，

即：a[i,j,k]-a[i,jj,k]-a[i,j,kk]，很多人认为这样就好了，但是你没注意细节，这样多减掉了一部分a[i,jj,kk]，还要在+回来才正确！

【样例程序】

program chixig;

 var h,m,n:integer;

     ans:int64;

     s:array[0..60] of longint;

     a:array[0..60,0..60,0..40] of integer;

 procedure init;

  var i,j,k:integer;

   begin

     assign(input,'chixig.in');reset(input);

     assign(output,'chixig.out');rewrite(output);

     readln(h,m,n);

     fillchar(a,sizeof(a),0);

     for k:=1 to h do

       begin

         for j:=1 to m do

           begin

             for i:=1 to n do read(a[i,j,k]);

             readln;

           end;

       end;

   end;

 procedure main;

  var i,j,jj,k,kk:integer;

      sum,temp:int64;

   begin

     for i:=1 to n do

       for j:=1 to m do

         for k:=1 to h do

           inc(a[i,j,k],a[i,j,k-1]);

     for i:=1 to n do

       for j:=1 to m do

         for k:=1 to h do

           inc(a[i,j,k],a[i,j-1,k]);

     ans:=-maxlongint;

     for k:=h downto 1 do

       for kk:=k-1 downto 0 do

         for j:=m downto 1 do

           for jj:=j-1 downto 0 do

             begin

               for i:=1 to n do s[i]:=a[i,j,k]-a[i,jj,k]-a[i,j,kk]+a[i,jj,kk];

               sum:=s[1];temp:=s[1];

               for i:=2 to n do

                 begin

                   if temp > 0 then inc(temp,s[i]) else temp:=s[i];

                   if temp > sum then sum:=temp;

                 end;

               if sum > ans then ans:=sum;

             end;

   end;

 procedure print;

  begin

    write(ans);

    close(input);close(output);

  end;

 begin

  init;

  main;

  print;

 end.