F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 1198. -- [HNOI2006]军机调度

1198: [HNOI2006]军机调度

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 382  Solved: 268
[Submit][Status][Discuss]

Description

凯萨拥有一支由n个人组成的雇佣军,他们靠在威尼斯商行接任务过活。这支军队的成份比较复杂,不同的人往往
具有不同的技能,有的人还拥有多项技能。威尼斯商行的任务也参差不齐,有的需要几个人合作完成,有的只需要
一个人独立完成:有的很简单,不需要耗多少时间,因此报酬也较低,有的很有难度,需要多个人长期合作完成,
因此报酬就高。完成这些任务的时间不会超过一个月。并且,一个人不能同时执行两项任务,也不能中途加入或者
退出任务。但可以不执行任何任务。一项只需要n个人来完成的任务,如果执行该任务的人数p大于n,那么反而会得
到更少的报酬,即原报酬的1/(p-n+1)。凯萨是一位英明的领袖,他往往在每个月的月底召开军事会议,总结上个
月的成果,发给大家报酬,并指派下个月的任务。请问,凯萨应该怎样指派任务,才能使总报酬最高?总报酬为多
少?

Input

一行包含两个正整数n,m。彼此用空格隔开,
其中n〈10表示雇佣军的人数,m〈15表示下个月可选的任务数。
接下来的n行中第i行(对应文件的第i+1行)的第一个整数小于等于表示编号为i的雇佣军可执行的任务数
后面的整数是编号为i的雇佣军可以执行的所有任务的编号,这些整数之间用空格隔开。
最后的m行中,每行有四个整数b、e、p和r,彼此之间用空格隔开,
其中第j行(对应整个文件的第n+j+1行)是编号为j的任务的描述:
0<b<32表示该任务的开始日(这一天会被计入任务所需的时间中),
0<e<32表示该任务的结束日(这一天也会被计入任务所需的时间中),
p<10表示该任务所需人数,0<r<100000表示该任务的报酬。

Output

第一行只有一个整数t,表示最多可获得的总报酬

Sample Input

3 5
2 1 4
2 2 4
3 3 4 5
2 20 1 100
1 18 1 200
3 28 1 800
21 30 3 1500
19 21 1 400

Sample Output

1800

HINT

Source

[Submit][Status][Discuss]

HOME Back