OpenJudge

1021:任务调度

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
30720kB
描述
一个单位时间任务是一个作业,如要在计算机上运行一个程序,它恰覆盖一个单位的运行时间。给定一个单位时间任务的集合S,对S的一个调度即S的一个排列,其中规定了这些任务的执行顺序。该调度中的第一个任务开始于时间0,结束于时1;第二个任务开始于时间1, 结束于时间2;……。单处理器上具有期限和罚款的单位时间任务调度问题的输入如下:
1.包含n个单位时间任务的集合S={1,2,……,n};
2.n个取整的期限d1,……,dn,(1≤d,≤n),任务i要求在di前完成;
3.n个非负的权(或罚款)w1,……,wn。如果任务i没在时间di之前结束,则导致罚款wi;
要求找出S的一个调度,使之最小化总的罚款。
输入
输入第一行为N<=1000,后面N行每行两个数,即为对应的di与wi。(wi<=1000)
输出
输出最小总罚款
样例输入
5
1 4
2 4
2 8
3 8
5 2
样例输出
4
全局题号
3246
添加于
2014-04-13
提交次数
1
尝试人数
1
通过人数
1