题目名称 814. 工作指派
输入输出 dividea.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-06-14
开放分组 全部用户
提交状态
分类标签
动态规划
通过:33, 提交:85, 通过率:38.82%
Gravatarkaaala 100 0.014 s C++
GravatarAAAAAAAAAA 100 0.055 s C++
GravatarZhouHang 100 0.124 s C++
GravatarShirry 100 0.177 s C++
GravatarArrow 100 0.183 s C++
GravatarFisher. 100 0.185 s C++
GravatarJoel_12 100 0.241 s C++
GravatarOIdiot 100 0.284 s C++
Gravatar1234 100 0.331 s C++
Gravatar1azyReaper 100 0.336 s C++
关于 工作指派 的讨论
(...)2 是平方啊...我还以为是×2呢
GravatarQhelDIV
2012-06-18 17:50 1楼
ORZ光神!
GravatarPaulinsider
2012-10-15 16:35 2楼
VIP 开long long !!!
Gravatar沉迷学习的假的Keller
2016-09-12 15:12 3楼
不写优化也能过?
GravatarShirry
2017-11-07 13:54 4楼
就。。。就这样过了??
Gravatarluo
2017-11-07 15:16 5楼

814. 工作指派

★☆   输入文件:dividea.in   输出文件:dividea.out   简单对比
时间限制:1 s   内存限制:128 MB

【问题描述】

小D有N份工作要完成,每一份工作有一个难度系数。由于工作数目太多了,小D光靠自己的能力是无法完成的,所以他打算雇佣很多工人很多人来帮他。工人是非常精明的,他们要求按照工作数目收费,如果分派给他的工作数目小于k,他们将不愿意接受。工人完成一份工作的收费是C。但是,小D也是很精明的老板,考虑到有些工作之间很类似,完成了一份工作之后可以很轻松的完成下一份工作,所以他提出了这样的要求,工人能够得到的报酬将是C + (maxB–minB)^2。其中,maxB表示工人接受的所有工作中的难度系数的最大值,minB是最小值。显然,如果工人只接受了一份工作,那么他将得到的报酬是C。
作为小D的助理,现在你需要告诉他,为了完成这些工作,他至少要支付多少钱给工人?

【输入文件】

       第一行三个非负整数N、k、C,意义如题所述;
       第二行N个正整数分别描述N份工作的难度系数。

【输出文件】

一个整数表示小D最少需要支付的工资。

【样例输入】

2 1 1
2 4

【样例输出】

2

【样例说明】

       如果分给一个工人做,收费为1 + (4–2)2 = 5;
如果分给两个工人作,收费为1 + 1 = 2;
所以最小收费为2。

【评分标准】

       本题包含10个测试点,对于每个测试点,如果你的输出和标准输出完全一样则得到该测试点的全部分数,否则得0分。

【数据规模】

       对于50%的测试数据,满足1 ≤ k ≤ N ≤ 20
对于100%的测试数据,满足
1 ≤ k ≤ N ≤ 10 000
              0 < C ≤ 1 000 000
              难度系数 ≤ 100 000 000