#P2654. 原核生物培养
原核生物培养
题目描述
W 教授最近正在研究一种原核生物,这种生物的生长方式很奇特,只能通过吃掉同类而生长。两个该种生物相遇,较大质量的会把较小的吃掉(相同的话就看 RP 了),吃掉后较大的生物的质量会变为两只原核生物重量之和,但这个过程会消耗酶,消耗的酶近似为它们重量之和。
W 教授现在有 只原核生物,他每次会从培养皿中取重量最小的 个生物进行实验,让它们自相残杀。
实验的操作是这样的,教授将这 个原核生物按某种重量大小的顺序放在一个环形的管道里,然后给其中相邻两只原核生物酶,如此反复。最后把剩下的那只放回培养皿,接着进行下次实验。W 教授希望经过 次实验后耗能最少。输入数据保证,不会出现生物不够的情况。
输入格式
第一行有三个整数,分别为 , , 。
第二行有 个整数,代表最初 个生物的重量。
接下来的 行,每行 个整数,第 行的第 个数代表第 次实验的第 小的生物放在哪个位置。例如 ,第三行为, 代表最小的生物放在第一个位置,第二小的放第三个 最大的放在第五个位置(和第一个位置相邻)。
输出格式
只有一个整数,代表 次实验之后最小消耗酶的量。
10 2 3
1 2 3 4 5 6 7 8 9 10
1 2
1 2
1 2
18
提示
对于 的数据,, , 。数据保证结果不超过 。
样例解释:
第一次是用重量为 消耗酶 ,变为一个重量 。
第二次是用重量为 消耗酶 ,变为一个重量 。
第三次是用重量为 消耗酶 ,变为一个重量 。
所以消耗总酶为 。