跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0225. #2292. 「THUSC 2016」成绩单

    ID: 231 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>待分类整理状态难度待定难度共享题库LibreOJ中文题面题目来源题面语言

#2292. 「THUSC 2016」成绩单

题目描述

期末考试结束了,班主任L老师要将成绩单分发到每位同学手中。L老师共有 份成绩单,按照编号从 到 的顺序叠放在桌子上,其中编号为 的成绩单分数为 。 成绩单是按照批次发放的。发放成绩单时,L老师会从当前的一叠成绩单中抽取连续的一段,让这些同学来领取自己的成绩单。当这批同学领取完毕后,L老师再从剩余的成绩单中抽取连续的一段,供下一批同学领取。经过若干批次的领取后,成绩单将被全部发放到同学手中。 然而,分发成绩单是一件令人头痛的事情,一方面要照顾同学们的心理情绪,不能让分数相差太远的同学在同一批领取成绩单;另一方面要考虑时间成本,尽量减少领取成绩单的批次数。对于一个分发成绩单的方案,我们定义其代价为:

其中 是分发的批次数,对于第 批分发的成绩单, 是最高分数, 是最低分数, 和 是给定的评估参数。 现在,请你帮助L老师找到代价最小的分发成绩单的方案,并将这个最小的代价告诉L老师。当然,分发成绩单的批次数 是由你决定的。

输入格式

第一行包含一个正整数 ,表示成绩单的数量。 第二行包含两个非负整数 ,表示给定的评估参数。 第三行包含 个正整数 , 表示第 张成绩单上的分数。

输出格式

仅一个正整数,表示最小的代价是多少。

样例

样例输入 1

10
3 1
7 10 9 10 6 7 10 7 1 2

样例输出 1

15

数据范围与提示


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 115 题。保留原作者与原赛事署名。