P1973 [NOI2011] NOI 嘉年华 题解（个人学习笔记）

考虑dp

若一个活动被选择，则其所包含的所有活动必属于同一嘉年华，所以dp一定是一块块转移

$sum_i,_j$ 表示i到j中区间数量，可$O(n^3)$预处理 对时间离散化 $pre_i,_j$ 表示考虑到时间i，某一嘉年华j场另一个最高多少

$suf_{i,j}$ 定义为从后往前，式子类似

均为$O(n^3)$

$f_{i,j}$ 表示时间i至j内必选

为$O(n^4)$

考虑优化

若对于某一x有最佳y，则x增加时y一定不增加，使用双指针，可$O(n^3)$