带权活动安排

• 问题：活动有开始时间、结束时间、权重。求互不兼容集合的最大权重。
• 预处理：按结束时间排序，计算 $p(j)$（在活动 $j$ 开始之前结束的最近一个活动的下标）。
• 转移方程： $OPT(j)=\max \{v_j+OPT(p(j)),OPT(j-1)\}$
  • 选 $j$：当前价值 + 前一个兼容活动的最优解。
  • 不选 $j$：继承 $j-1$ 的最优解。