区间型动态规划
P7914 [CSP-S 2021] 括号序列
细节处理
\(AB\)，\(ASB\) 部分可能算重（如(**)()*(())会被每一个分界点统计），需要强制确定是第一部分取
关路灯
[P5336] 成绩单
P1864 [NOI2009] 二叉查找树
区间DP
一开始想到的是直接\(f(l,r,dep)\)表示\([l,r]\)形成的子树，枚举根，并把根的权值拉到最小，时间复杂度\(O(n^4)\)
结果\(30pts\)
后面分析了一下，“把根的权值拉到最小”不一定优，有可能把别的点权拉大更优
不妨直接考虑根节点的权值，设\(f(l,r,k)\)表示\([l,r]\)根节点权值\(\ge k\)的子树代价（注意不能是\(=k\)，因为权值可以设为任意实数，所以可以无限接近\(k\)），而\(dep\)完全不用压进状态
考虑根节点是否改变权值，转移即可