RQNOJ系统遇到了一个程序错误。

您可以通过邮件support (at) rqnoj.cn与我们进行联系。请附错误参考编号:273337

Orz细菌 - 题库 - RQNOJ
PID392 / Orz细菌
题目描述

话说由于余震的威胁,JDC和全校同学地震当晚只能睡在操场上。JDC睡在操场上,迷迷糊糊就进入了梦想,他做了这样一个梦:

JW老师最近正在研究一种新型细菌,名为ORZ细菌,这种细菌的生长方式很特别,它们只能通过吞噬同类才能长大(那它们是怎么产生的呢?)。两个orz细菌相遇后,较大的细菌会把较小的细菌吞噬(相同的话就看这两只细菌的RP了),吞噬后较大的细菌的体积会变为两只细菌体积之和,但这个过程会消耗能量,为了方便计算,消耗的能量近似为它们体积之和。

JW老师现在有n只细菌,他每回会从培养皿中取体积为前m小的细菌进行实验,让它们互相吞噬(残忍!)。实验的操作是这样的,JW老师将这m只细菌按体积大小放在一个环形的管道里,再给以细菌刺激,以加快或减慢相邻两只细菌相互吞噬的速度(我们认为这个加速度是无穷大的)。最后把幸存的那只细菌放回培养皿,再进行下次实验。由于细菌吞噬的能量要JW老师来提供,所以他希望经过k次实验后消耗的能量最少。输入数据保证,不会出现细菌不够的情况。

数据规模

1<n<=100000,1<=m<=10,1<=k<=10000

数据保证结果不超过2^31

样例说明(不用输出)

第一次是用体积为1 2的细菌 最终消耗能量3 变为一个体积为3的细菌

第二次是用体积为3 3的细菌 最终消耗能量6 变为一个体积为6的细菌

第三次是用体积为4 5的细菌 最终消耗能量9 变为一个体积为9的细菌

所以消耗总能量为18

输入格式

第一行有三个整数,分别为n,m,k

第二行有n个整数,代表最初n个细菌的体积

接下来的k行,每行m个整数,第i+2行的第j个数代表第i次实验的第j小的细菌放在哪个位置。例如m=5,第三行为,14235 代表最小的细菌放在第一个位置,第二小的细菌放在第四个位置…最大的细菌放在第五个位置(和第一个位置相邻)

输出格式

只有一个整数,代表k次实验之后消耗的最小能量。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论