1973（DP，双指针）
注意：题目中的区间 \((l,r)\) 是开区间！
\(pre(i,j)\) 表示前 \(i\) 个位置，某个地点选了 \(j\) 个活动，另一个地点所能选的活动数量的最大值。
\(suf(i,j)\) 表示后 \(i\) 个位置，某个地点选了 \(j\) 个活动，另一个地点所能选的活动数量的最大值。
\(w(i,j)\) 表示区间 \(i\) 到 \(j\) 的活动数量。
\[pre(i,j)=\max_{k<i}\{pre(k,j)+w(k,i),pre(k,j-w(k,i))\} \]\[suf(i,j)=\max_{k>i}\{suf(k,j)+w(i,k),suf(k,j-w(i,k))\} \]设 \(tot\) 为离散化后时间序列的长度，第一问的答案为
\[\max_{i=0}^{n}\min(i,pre(tot,i)) \]设 \(f(l,r)\) 表示钦定某个地点钦定选择 \((l,r)\) 区间里的所有活动，两个地点最小活动的最大值
\[f(l,r)=\max_{0\leq x\leq n,0\leq y\leq n}\min(x+y+w(l,r),pre(l,x)+suf(r,y)) \]但是有可能存在跨越端点的活动，因此
\[ans(l,r)=\max_{x\leq l,y\geq r}f(x,y) \]需要预处理出所有的 \(f(l,r)\)，暴力处理复杂度是 \(\mathcal{O}(n^4)\)，考虑优化。
发现如果把 \(pre(i,j)\) 和 \(suf(i,j)\) 的定义都改成至少选 \(j\) 个对最后 \(f(l,r)\) 计算没有影响。
改了之后就 \(x\) 增大时 \(y\) 就一定不增了，这样就优化到了 \(\mathcal{O}(n^3)\)。
标签：pre,suf,luogu,地点,leq,max,活动 From： https://www.cnblogs.com/yanchengzhi/p/17002005.html