果然\(DP\)杀我
这个数据范围一脸区间\(DP\)的杨子，确实有关系
我们发现如果一个场地选了活动\(n\)，那么\([s[i],t[i]]\)内的所有活动应该都选了
限离散化时间，统计\(tot[l][r]\)内活动总数
设\(pre[i][j]\)为\(1-i\)时间内第一个场地选\(j\)个活动，第二个场地能举办的最多的活动数
我们需要枚举时间段来转移，枚举\(1<=k<=i\)
讨论\([k,i]\)时间内的活动放到第一个场地还是第二个场地
\(pre[i][j]=min(pre[k][j]+tot[k][i],pre[k][i-tot[l][r]])\)
我们再用同样方式算出\(suf[i][j]\)表示\(i-m\)时间内第一个场地选\(j\)个活动，第二个场地能举办的最多的活动数
设\(f[l][r]\)表示\([l,r]\)内的活动在第一个场地内进行，两个场地活动数的最小值
可以枚举第一个场地在\(l\)之前选了\(x\)个活动，\(r\)之后选了\(y\)个活动 得到转移
\(f[l][r]=min(x+tot[l][r]+y,pre[l][x]+suf[r][y])\)
考虑当\(x\)变大时，如果\(y\)也变大，必然导致后面那一项减少，所以当\(x\)变大时\(y\)只要变小，求\(f\)数组的复杂度可以降低到\(O(n^3)\)
那么当没有要求时\(ret=max\{min(pre[m][i],i)\}\)
当有要求时，我们枚举所有包含\([s[i],t[i]]\)的区间，求\(f[l][r]\)的最大值
原文：https://www.cnblogs.com/knife-rose/p/12618739.html