#PQJ402x2999. QOJ 402_2999
QOJ 402_2999
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试春节十二响(spring) 春节十二响(spring) 【题目背景】 “清明时节雨纷纷,路上行人欲断魂。” 2075 年的清明没有春雨。在漫天飞雪的笼罩下,穿行在冰原间的,只有载着人类 微薄希望的雪地车。 遥遥4.22 光年的征途,对于地球这孤独的旅人而言,恐怕也是无比寂寞的吧。 【题目描述】 距离苏拉威西只有一百公里了,车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉 芬面前的屏幕,那是控制行星发动机的关键程序:春节十二响。他需要将其部署到电力 控制系统的一个芯片中。 “春节十二响”由n 个子程序构成,第i 个子程序所需的内存空间是Mi。这n 个 子程序之间的调用关系构成了一棵以第1 个子程序为根的树,其中第i 个子程序在调 用树上的父亲是第fi 个子程序。 由于内存紧张,电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干 个段S 1, S 2, . . . , S k,并将每个程序预先分配到一个固定的段。如果两个子程序没有直接 或间接的调用关系,则他们可以被分配到同一个段中,反之则不能。换言之,当且仅当 a 和b 在调用树上.不.是.祖.先- .后.代.关.系,a 和b 可以被分配到同一个段中。 一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值,所有段 大小的和不能超过系统的内存大小。 现在艾莉芬想要知道,电力控制芯片至少要有多少内存,才能保证春节十二响的正 确运行。即:最少需要多大的内存,才能通过先.将.内.存.分.成.若.干.个.段,再.把.每.个.子.程.序 .分.配.到.一.个.段.中,使得.每.个.段.中.分.配.的.所.有.子.程.序.之.间.不.存.在.祖.先- .后.代.关.系。 【输入格式】 从文件spring.in 中读入数据。 第一行包含一个正整数n 表示子程序的个数,其中n ≤2 × 105。 第二行有n 个用空格隔开的正整数M1, M2, . . . , Mn,Mi 表示第i 个子程序所需的 内存空间。 第三行有n −1 个用空格隔开的正整数f2, f3, . . . , fn,满足fi < i,表示第i 个子程 序在调用树上的父亲是第fi 个子程序。 【输出格式】 输出到文件spring.out 中。 第6 页 共13 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试春节十二响(spring) 仅一个整数,表示最小的内存需求。 【样例1 输入】 5 10 20 20 30 30 1 1 2 2 【样例1 输出】 60 【样例1 解释】 在最优方案中,内存被划分为大小为10,20,30 的三个段,其中第1 个子程序被 分配在第1 个段中,第2、3 个子程序被分配在第2 个段中,第4、5 个子程序被分配 在第3 个段中。可以证明,不存在更优的方案。 【样例2】 见选手目录下的spring/spring2.in 与spring/spring2.ans。 【样例3】 见选手目录下的spring/spring3.in 与spring/spring3.ans。 【子任务】 测试点 n M 是否是一条链 1,2 ≤5 ≤10 否 3,4 ≤10 ≤2 否 5,6,7,8,9 ≤16 ≤109 否 10,11,12 ≤2 × 105 ≤109 是 13,14,15 ≤2, 000 ≤109 否 16,17,18,19,20 ≤2 × 105 ≤109 否 注意:在第10、11、12 号测试点中,1 号子程序.不.一.定是链的一个端点。 其中M 是所有子内存需求的最大值,即max{Mi}。 对于全部数据,1 ≤n ≤2 × 105,1 ≤M ≤109。 第7 页 共13 页
2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第二试春节十二响(spring) 【提示】 艾莉芬经过.仔.细.阅.读.题.面、.认.真.分.析.数.据.范.围后,开始编写程序求解这个问题。 $ login Elephant password: ******** 艾莉芬,高级程序员。豫阳市第三工程组提醒您:
- 做题千万条,读题第一条;
- 编程不规范,爆零两行泪。 ac spring Spring Accepted. Score: 100/100. 第8 页 共13 页