2011福建省信息学奥林匹克 CCF NOIP夏令营第八天训练
问题名称 文件名 输入文件 输出文件 时限 分值 最大子段和 maxsum1 maxsum1.in
maxsum1.out 1s 100 环状最大两段 maxsum2 maxsum2.in maxsum2.out 1s 100 子段和
最大子树和 maxsum3 maxsum3.in maxsum3.out 1s 100 内存限制均为 256M 最大子段和 (maxsum1)
【问题描述】 给出一段序列，选出其中连续且非空的一段使得这段和最大。 【输入文件】
输入文件maxsuml.in的第一行是一个正整数N,表示了序列的长度。 包含N个绝对值不大于10000的整数A[i]，描述了这段序列。
【输出文件】
输入文件maxsuml.out仅包括1个正整数，为最大的子段和是多少。 【样例输入】
第2行
7
2 -4 3 -1 2 -4 3
【样例输出】
4
【样例说明】
2 -4 3 -1 2 -4 3 【数据规模与约定】
对于 40%的数据，有 N ? 2000。 对于 100%的数据，有 N ? 200000。
题目大意 : 在一个序列中找出一个段连续非空和最大
设 f[i] 为取第 i 个时的最大值，那么 f[i]:=max(map[i],map[i]+f[i-1]); Max(f[i]) 即为所求。
var a,ans:array[1..200000] of int64; n,i:longint; max:int64;
begin assign(input,'maxsum1.in');
assign(output,'maxsum1.out'); reset(input); rewrite(output); readln(n); read(a[1]); ans[1]:=a[1];
for i:=2 to n do begin read(a[i]); if ans[i-1]<0 then ans[i]:=a[i] else ans[i]:=ans[i-1]+a[i]; end;
max:=-maxlongint; for i:=1 to n do
if ans[i]>max then max:=ans[i]; writeln(max); close(input); close(output); end.
环状最大两段子段和 (maxsum2) 【问题描述】
给出一段环状序列，即认为 A[1] 和 A[N] 是相邻的，选出其中连续不重叠且非 空的两段使得这两段和最大。
【输入文件】
输入文件maxsum2.in的第一行是一个正整数N,表示了序列的长度。 第2行 包含N个绝对值不大于10000的整数A[i]，描述了这段序列，第一个数和第 N个 数是相邻的。
【输出文件】
输入文件maxsum2.out仅包括1个整数，为最大的两段子段和是多少。 【样例输入】
7
2 -4 3 -1 2 -4 3
【样例输出】
9
【样例说明】
一段为3 - 1 2，一段为3 2
2 -4 3 -1 2 -4 3
【数据规模与约定】
对于 40%的数据，有 2 ? N ? 2000 。 对于 100%的数据，有 N ? 200000。
题目大意 : 在一个环状序列中取两段非空且和最大。 这题很有难度，如何破环为链 , 用到第一题的方法 , 可以发现，结果无非只有两种情况。
————— | ——— | —————— | ————— | —————
1、 取到的两段在中间，则枚举切割点，分成两段，分别用第一题方法求解， 取和最大。
————— | ——— | —————— | ————— | —————
2、 取到的两段一段在中间，一段在首尾。
发现图 2与图 1很相似，如果枚举 3段红色部分可能会超时。于是可以枚举两 段黑色部分，即找两段连续非空和最小，然后用总和减去这两段黑色部分，再取最 大值。 ( 注意如果总和
-黑色=0 说明全都不取，而如果都是负数就会出错 ); 也可以 全部取负，然后取最大。。
var
zheng,fu,zhengmax,fanmax,fumax,fufanmax:array[0..200001] of longint;
fan,fufan:array[0..200001] of longint; map,fumap:array[0..200000] of longint; i,n,sum,maxans,temp:longint; function max(a,b:longint):longint; begin
if a>b then exit(a) else exit(b); end; begin
assign(input,'maxsum2.in'); assign(output,'maxsum2.out'); reset(input); rewrite(output); readln(n); sum:=0;
for i:=1 to n do begin read(map[i]); fumap[i]:=-map[i]; inc(sum,map[i]); end;
zheng[1]:=map[1]; zhengmax[1]:=map[1]; fu[1]:=fumap[1]; fumax[1]:=fumap[1]; for i:=2 to n do begin
if zheng[i-1]>=0 then zheng[i]:=zheng[i-1]+map[i] else zheng[i]:=map[i];
zhengmax[i]:=max(zhengmax[i-1],zheng[i]); if fu[i-1]>=0 then fu[i]:=fu[i-1]+fumap[i] else fu[i]:=fumap[i];
fumax[i]:=max(fumax[i-1],fu[i]);
end; fan[n]:=map[n]; fanmax[n]:=map[n]; fufan[n]:=fumap[n];
fufanmax[n]:=fumap[n]; for i:=n-1 downto 1 do begin
if fan[i+1]>=0 then fan[i]:=fan[i+1]+map[i] else fan[i]:=map[i]; fanmax[i]:=max(fanmax[i+1],fan[i]);
if fufan[i+1]>=0 then fufan[i]:=fufan[i+1]+fumap[i] else fufan[i]:=fumap[i]; fufanmax[i]:=max(fufanmax[i+1],fufan[i]); end;
maxans:=-maxlongint; for i:=1 to n-1 do begin
temp:=zhengmax[i]+fanmax[i+1]; if temp>maxans then maxans:=temp; temp:=fumax[i]+fufanmax[i+1];
if (sum+temp>maxans) and (sum+temp<>0) then maxans:=sum+temp; end;
writeln(maxans);
close(input); close(output); end.
最大子树和 (maxsum3)
【问题描述】 小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师 请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿 时想到了一个有关修剪花卉的问题。于是当日课后，小明就 向老师提出了这个问 题:
一株奇怪的花卉，上面共连有 N 朵花，共有 N-1 条枝干将花儿连在一起，并且 未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵 花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修 剪”，意为 : 去掉其中的一条枝条，这样
2011福建省信息学奥林匹克CCFNOIP夏令营第八天训练
