【BZOJ2034】最大收益 贪心

题目链接

好神的一道题,看一眼就知道是贪心,可能要按照权值排序,然后。。。就没有然后了。

听了小胖子讲课,又%%%了09年集训队爷冯齐纬的解题报告,果然这个方法非常神奇。

在这里简述,具体事项自己看论文。

首先找到n个活跃点,活跃点满足左端点第i小的任务,其左端点右侧至少有n-i+1个活跃点,具体做法是先将区间左端点排序,然后枚举每个区间,将左端点右侧第一个非活跃点变为活跃点即可。这样可以得到n个活跃点。

论文里证明了任务只安排在活跃点不影响最优答案。然后就看怎么安排了。

先将任务按照收益从大到小排序,然后依次判断能不能放,判断使用这个函数(想出这个办法的真的好厉害)。

然后就这样我们可以O(n^2)地解决这道题了~

完整代码如下:

 

 

 

不如来评论一发?