P1973 [NOI2011] NOI 嘉年华 题解（个人学习笔记） shaun2000 · 2025-10-17 21:19:32 · 题解 考虑dp 若一个活动被选择，则其所包含的所有活动必属于同一嘉年华，所以dp一定是一块块转移 对时间离散化 $pre_i,_j$ 表示考虑到时间i，某一嘉年华j场另一个最高多少 $ pre_i,_j=max(pre_k,_j+ sum_{k,i} , pre_{k,j- sum_{k,i}}) 均为$O(n^3) $ans_i=max(f_{l,r}) ( l<=L_i r>=R_i ) f_{i,j}=max( min( sum_i,_j+ x+y ,pre_{i,x}+suf_{j,y} ) ) 为O(n^4) 考虑优化 若对于某一x有最佳y，则x增加时y一定不增加，使用双指针，可O(n^3)