3614: 工作指派 -训练套题T6T3
Description
3. 工作指派 (divide.pas/c/cpp)
【问题描述】
小D有N份工作要完成，每一份工作有一个难度系数。由于工作数目太多了，小D光靠自己的能力是无法完成的，所以他打算雇佣很多工人很多人来帮他。工人是非常精明的，他们要求按照工作数目收费，如果分派给他的工作数目小于k，他们将不愿意接受。工人完成一份工作的收费是C。但是，小D也是很精明的老板，考虑到有些工作之间很类似，完成了一份工作之后可以很轻松的完成下一份工作，所以他提出了这样的要求，工人能够得到的报酬将是C + (maxB–minB)^2。其中，maxB表示工人接受的所有工作中的难度系数的最大值，minB是最小值。显然，如果工人只接受了一份工作，那么他将得到的报酬是C。
作为小D的助理，现在你需要告诉他，为了完成这些工作，他至少要支付多少钱给工人？
【输入】
第一行三个非负整数N、k、C，意义如题所述；
第二行N个正整数分别描述N份工作的难度系数。
【输出】
一个整数表示小D最少需要支付的工资。
【输入输出样例】
|
divide.in |
divide.out |
|
2 1 1 2 4 |
2 |
【输入输出样例说明】
如果分给一个工人做，收费为1 + (4–2)^2 = 5；
如果分给两个工人作，收费为1 + 1 = 2；
所以最小收费为2。
【数据规模】
对于50%的测试数据，满足1 ≤ k ≤ N ≤ 20
对于100%的测试数据，满足1 ≤ k ≤ N ≤ 10 000，0 < C ≤ 1 000 000， 难度系数 ≤ 100 000 000 （最后一个数据超过此范围，应该用qword）HINT
工作指派
【题目大意】
有N份工作每份工作有一个难度系数。现在要将其分为若干个不相交的集合，使得每份工作恰好出现在其中一个集合中且每个集合中包含的工作个数不小于K。每个集合的费用定义为：
|
证明： 否则，一定最优解中存在a < b < c < d使得Ba、Bc是同一个工人完成的，Bb、Bd是另一个工人完成的。那么，因为(Bd – Bc)2 + (Bb – Ba)2 <= (Bc – Ba)2 + (Bd – Bb)2，所以让第一个工人完成工作Ba、Bb，第二个工人完成工作Bc、Bd不会让解变得更差。这样，经过有限次调整之后使得最优解满足我们的假设。 |
有了这个结论，我们可以采取一个最简单的动态规划来解决这个题目。
以minCost[T]描述将B1、B2 …… BT划分为若干个集合的最小花费，那么由转移方程：
这个算法的时间复杂度为O(N2)，可以很好的解决本题了。
另外，本题存在线性时间内的解决方法，需要利用数形结合单调性的相关知识，建议有兴趣的读者研究2004年冬令营周源的论文《数形结合》（推荐）或者2007年冬令营杨哲的论文。