看这篇题解
对这篇题解做一些解释
首先看到这道题目，时间范围很大，所以我们先考虑如何对区间进行排序，但是你会发现无论是按照左端点排序还是按照右端点排序，都很难DP下去，所以我们只能对时间排序，然而时间非常大，要对时间进行排序，就必须要离散化（这里启发我们，不要太固定思维觉得大的时间无法排序），设离散化之后的时间范围为\([1,T]\)，其中\(1≤T≤2n\)
按照时间排序之后，有一个好处，因为题目要求不能相交，所以分在一个嘉年华的活动的起始和终止时间一定是一段一段的（这个起始和终止时间不一定要与某个区间的左右端点重合，比如就考虑把\([l,r]\)时间范围内的所有活动全部分给某一个嘉年华，不用考虑\(l\)或\(r\)是哪个区间的端点）
然后来看第一问，还有一个固定思维就是觉得DP的某一维应该设置差值，但还是发现推不出来，所以也不要固执了，直接像题解这么设
然后题解对第一问DP方程的推导，比如第一种情况
这个方程的意思是\([k+1,r]\)的所有活动全部放到第一个嘉年华里面，但是有没有可能我只放一部分呢？其实是不用担心的，如果只放一部分，假设有\(x\)个，我们完全可以选择\([k+1,r]\)中的最后\(x\)个，仍然不会遗漏最终的答案
然后是题解对第二问的处理，这个跟北大ACM队的远足这道题目的trick是一样的
然后是题解在推导\(s(l,r)\)的时候，不用向他这么理解。此时\(l,r\)是定值所以\(c\)是常数，假设\(k\)定了，那么随着\(t\)增大，前面一项在减少，后面一项在增加，那么中间就存在交点，设交点在\(t=t_0\)时相交，当\(k\)增大后，显然\(t_0\)也会增大，所以这是单调的；而对每一个\(k\)，取交点处肯定是最优的，所以利用单调队列优化就好了
标签：嘉年华,NOI,题解,时间,端点,排序,DP From： https://www.cnblogs.com/dingxingdi/p/18045321