Luogu P7503 「HMOI R1」文化课

标签：le R1 P7503 Luogu max HMOI

题传

先想一个巨 shaber 的暴力 DP：设 \(f_{i}\) 为对前 \(i\) 个人分段的最优解，则：

\[f_{i}=\max_{0\le j<i}\{f_{j}+\operatorname{W}(j+1, i)\} \]

其中：

\[\operatorname{W}(x, y)=\sum_{i=x}^y [l_i \le \max(x_j|j\in [x, y]) \le r_i] \]

暴力做显然是 \((n^2)\) 的，考虑优化。

如果考虑将决策中的 \(i\) 右移一位，用线段树维护 \(val_i(x)=f_{x-1}+\operatorname{W}(x, i)\) 的话，发现右移时无法快速修改有变化的位置（类似 \(+1\ 0\ 0\ +1\dots\) 状物，不好维护）。

正难则反，考虑某个 \(j\) 会对哪些决策位置 \((x, i)\) 有贡献。

标签：le,R1,P7503,Luogu,max,HMOI
From： https://www.cnblogs.com/sizeof127/p/16748074.html