题目描述
给定 个区间 和权值 。选择若干两两不相交的区间,使总权值最大。
端点相接视为相容。
,,。
题解
按右端点 升序排序。设排序后第 个区间为 ,定义 为最大的下标 ,使得 ;不存在则 。由于右端点有序,可以用二分求 。
令 表示只考虑前 个区间时的最大总权值。对第 个区间只有两种选择:
因此
答案为 。
正确性来自最优子结构:若最优解选择 ,它前面的区间必须全部在 左侧结束,正好是前 个区间;若不选,则最优解来自前 个区间。
复杂度
排序为 ,每个 二分查找为 ,DP 为 。总时间为 ,空间为 。
参考