福建2010Noip夏令营day8

测试时间：14:00-16:30 16:30之后提交的程序一概不收

提交方式不变

问题名称 最大和 修剪花卉 金字塔 文件名 sum makeup pyramid 输入文件 sum.in makeup.in pyramid.in 内存限制均为256M

输出文件 sum.out makeup.out pyramid.out 时限 分值 1s 100 1s 100 1s 100 最大和(max)

题目描述;

N个数围成一圈，要求从中选择若干个连续的数（注意每个数最多只能选一次）加起来，问能形成的最大的和。

输入格式：

第一行输入N，表示数字的个数，第二行输入这N个数字。

输出格式：

输出最大和。

样例输入： 8

2 -4 6 -1 -4 8 -1 3 样例输出： 14

数据说明： 40% 1<=N<=300 60% 1<=N<=2000

100% 1<= N<=100000,答案在longint范围内。

修剪花卉

程序名：makeup.* 时间限制：1秒 输入：makeup.in 内存限制：32M 输出：makeup.out 问题背景：

ZZ对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。 一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。

于是当日课后，ZZ就向老师提出了这个问题：

一株奇怪的花卉，上面共连有N 朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每 朵花都不是孤立的。

每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的， 说明这朵花看着都让人恶心。

所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。 经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。 老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那 朵）花卉上所有花朵的“美丽指数”之和最大。

老师想了一会儿，给出了正解（交大的老师是很牛的~）。ZZ见问题被轻易攻破，相当不爽， 于是又拿来问你。

输入说明：

第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N 朵花。

第二行有N 个整数，第I个整数表示第I朵花的美丽指数。

接下来N-1行每行两个整数a,b，表示存在一条连接第a 朵花和第b朵花的枝条。 输出说明：

一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超 过2147483647。 样例输入： 7

-1 -1 -1 1 1 1 0 1 4 2 5 3 6 4 7 5 7 6 7

样例输出： 3

数据范围：

对于 60%的数据， 保证N≤1,000 对于100%的数据，保证N≤16,000

金字塔(pyramid)

题目描述：

小X来到一个雄奇的金字塔挖宝，但是这是一座被诅咒的金字塔，小X必须马上逃离这里，否则小X就会被埋在金字塔里，但他不希望此行落空。

现在小X面前有N+1种财宝，每种财宝都有一个价值。第一种财宝重量为0，第二种财宝重量为1，总之第I种财宝重量为I-1。现在小X希望拿走N+M个物品，但是这M+N个物品总重量不能超过N。小X希望能获得最大的价值。你能帮帮他吗？ 由于金字塔跟小X一样牛，所以每种财宝无限个。

输入格式：

第一行两个正整数N，M

第二行N+1个整数，第I个整数代表了第I种财宝的价值

输出格式：

一个数，表示最大利润。

样例输入： 5 3

4 7 2 5 -3 6

样例输出： 47

数据范围：

10%满足N,M<=10

40%满足N,M<=100

100%满足 N,M<=3000 abs(财宝价值)<=1000

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库福建2010Noip夏令营day8在线全文阅读。