2011福建省信息学奥林匹克CCFNOIP夏令营第八天训练

1、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,表示了序列的长度。第2

2、行 包含N个绝对值不大于10000的整数Ai，描述了这段序列。 【输出文件】 输入文件maxsuml.out仅包括1个正整数，为最大的子段和是多少。 【样例输入】 7 2 -4 3 -1 2 -4 3 【样例输出】 4 【样例说明】 2 -4 3 -1 2 -4 3 【数据规模与约定】 对于 40%的数据，有 N ? 2000。 对于 100%的数据，有 N ? 200000。 题目大意 : 在一个序列中找出一个段连续非空和最大 设 fi 为取第 i 个时的最大值，那么 fi:=max(mapi,mapi+fi-1); Max(fi) 即为所求。 var a,ans:array1.200000

3、 of int64; n,i:longint; max:int64; begin assign(input,maxsum1.in); assign(output,maxsum1.out); reset(input); rewrite(output); readln(n); read(a1); ans1:=a1; for i:=2 to n do begin read(ai); if ansi-1max then max:=ansi; writeln(max); close(input); close(output); end. 环状最大两段子段和 (maxsum2) 【问题描述】 给出一段环状

4、序列，即认为 A1 和 AN 是相邻的，选出其中连续不重叠且非 空的两段使得这两段和最大。 【输入文件】 输入文件maxsum2.in的第一行是一个正整数N,表示了序列的长度。 第2行 包含N个绝对值不大于10000的整数Ai，描述了这段序列，第一个数和第 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 。 对于

5、100%的数据，有 N ? 200000。 题目大意 : 在一个环状序列中取两段非空且和最大。 这题很有难度，如何破环为链 , 用到第一题的方法 , 可以发现，结果无非只有两种情况。 | | | | 1、 取到的两段在中间，则枚举切割点，分成两段，分别用第一题方法求解， 取和最大。 | | | | 2、 取到的两段一段在中间，一段在首尾。 发现图 2与图 1很相似，如果枚举 3段红色部分可能会超时。于是可以枚举两 段黑色部分，即找两段连续非空和最小，然后用总和减去这两段黑色部分，再取最 大值。 ( 注意如果总和 -黑色=0 说明全都不取，而如果都是负数就会出错 ); 也可以 全部取负，然后取最

6、大。 var zheng,fu,zhengmax,fanmax,fumax,fufanmax:array0.200001 of longint; fan,fufan:array0.200001 of longint; map,fumap:array0.200000 of longint; i,n,sum,maxans,temp:longint; function max(a,b:longint):longint; begin if ab then exit(a) else exit(b); end; begin assign(input,maxsum2.in); assign(output,m

7、axsum2.out); reset(input); rewrite(output); readln(n); sum:=0; for i:=1 to n do begin read(mapi); fumapi:=-mapi; inc(sum,mapi); end; zheng1:=map1; zhengmax1:=map1; fu1:=fumap1; fumax1:=fumap1; for i:=2 to n do begin if zhengi-1=0 then zhengi:=zhengi-1+mapi else zhengi:=mapi; zhengmaxi:=max(zhengmaxi

8、-1,zhengi); if fui-1=0 then fui:=fui-1+fumapi else fui:=fumapi; fumaxi:=max(fumaxi-1,fui); end; fann:=mapn; fanmaxn:=mapn; fufann:=fumapn; fufanmaxn:=fumapn; for i:=n-1 downto 1 do begin if fani+1=0 then fani:=fani+1+mapi else fani:=mapi; fanmaxi:=max(fanmaxi+1,fani); if fufani+1=0 then fufani:=fufa

9、ni+1+fumapi else fufani:=fumapi; fufanmaxi:=max(fufanmaxi+1,fufani); end; maxans:=-maxlongint; for i:=1 to n-1 do begin temp:=zhengmaxi+fanmaxi+1; if tempmaxans then maxans:=temp; temp:=fumaxi+fufanmaxi+1; if (sum+tempmaxans) and (sum+temp0) then maxans:=sum+temp; end; writeln(maxans); close(input);

10、 close(output); end. 最大子树和 (maxsum3) 【问题描述】 小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师 请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿 时想到了一个有关修剪花卉的问题。于是当日课后，小明就 向老师提出了这个问 题: 一株奇怪的花卉，上面共连有 N 朵花，共有 N-1 条枝干将花儿连在一起，并且 未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵 花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修 剪”，意为 : 去掉其中的一条枝条，这样一株花就成了两株，扔掉

11、其中一株。经过 一系列“修剪“之后，还剩下最后一株花 (也可能是一朵 ) 。老师的任务就是 :通过 一系列“修剪” （也可以什么“修剪”都不进行 ） ，使剩下的那株 （ 那朵） 花卉上所有 花朵的“美丽指数”之和最大。 老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿 来问你。 【输入文件】 输入文件 maxsum3.in 的第一行一个整数 N（1 ? N ? 16000） 。表示原始的那株 花卉上共 N 朵花。 第二行有 N 个整数，第 I 个整数表示第 I 朵花的美丽指数。 接下来 N-1 行每行两个整数 a,b ，表示存在一条连接第 a 朵花和第 b 朵花的枝 条。

12、【输出文件】 输出文件 maxsum3.out 仅包括一个数，表示一系列“修剪”之后所能得到的 “美丽指数”之和的最大值。保证绝对值不超过 2147483647。 【样例输入】 5 7 -1 -1 -1 1 1 1 0 1 4 2 5 3 6 4 7 5 7 6 7 样例输出】 3 【数据规模与约定】 对于 60%的数据，有 N?1000; 对于 100%的数据，有 N?16000。 题目大意 : 在一个无环无向图中 ( 也可以叫树 ) 删去一些边 ( 及边上带的顶点 ) ， 使剩下的顶点上的值最大。 树形DP设fi为取i这个顶点的美学最大值。Fi初始都为mapi,贝U对于 所有与 i 相连的

13、点 fj, 如果 fj0 就加入到 fi 否则不加。注意 fj 不能再遍 历 i. 最后 max(fi) 即为所求。 var ans,a,son,next,y:array0.32001 of longint; bb:array0.16001 of boolean; n,i,j,k,l,max:longint; procedure maketree; begin assign(input,maxsum3.in); assign(output,maxsum3.out); reset(input); rewrite(output); readln(n); for i:=1 to n do begin

14、 read(ai); ansi:=ai; end; readln; l:=0; fillchar(son,sizeof(son),0); fillchar(next,sizeof(next),0); fillchar(y,sizeof(y),0); for i:=1 to n-1 do begin readln(j,k); inc(l); nextl:=sonj; yl:=k; sonj:=l; inc(l); nextl:=sonk; yl:=j; sonk:=l; end; end; procedure tree(k:longint); var i,j,erzi,bian:longint; begin bbk:=true; bian:=sonk; while bian0 do begin erzi:=ybian; if bberzi=false then begin tree(erz