1 solutions
-
0
Guest MOD
- 1
Information
- ID
- 324
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 16
- Accepted
- 4
- Uploaded By
对于 20%的数据,n<=15;
枚举要做哪些作业,判断是否可行。 可行只需要满足:对于任意的 i,小于 i 的Di的数量不能超过 i 个。 O(n*2^n) 对于 60%的数据,n<=1000; 考虑一个贪心:对于最后一个单位时间,把这时能做的分数最大的作业做掉。依此倒着向前贪心,每次选最大的。 证明:若最优方案该作业不在这一时刻做,那么可以把这个作业和原方案中这一时刻做的作业换过来,也是一个合法方案。 朴素的实现方法可以得到60分。
若使用vector和priority_queue,时间复杂度为O(nlogn),得分100分。
By signing up a Hydro universal account, you can submit code and join discussions in all online judging services provided by us.