【杂题乱写】12 月北京省选 DP 专题训练

标签：12 min 乱写 Luogu 省选 le 区间 DP

有一部分题目是模板题，就不放了。

D. Luogu-P5336 THUSC 2016 成绩单

考虑区间 DP，由于操作的特殊性，我们需要设计含有区间最值的状态，设 \(f_{l,r,i,j}\) 表示区间 \([l,r]\) 中的所有数只保留值域 \([i,j]\) 中的最小代价，\(g_{l,r}\) 为将区间 \([l,r]\) 的所有数都删去的最小代价。

\(g_{l,r}\) 的转移非常简单，就是直接枚举最后删的区间，设值域为 \([1,m]\)，方程：

\[g_{l,r}=\min_{1\le i\le j\le m}\{f_{l,r,i,j}+a+b(j-i)^2\} \]

而 \(f_{l,r,i,j}\) 是枚举断点，左右区间可以选择直接删去或是变成子问题：

\[f_{l,r,i,j}=\min_{p=l}^{r-1} \{\min(g_{l,p}+f_{p+1,r,i,j},f_{l,p,i,j}+g_{p+1,r},f_{l,p,i,j}+f_{p+1,r,i,j})\} \]

提交记录：Submission - Luogu

吃饭去了，其他下午写。

标签：12,min,乱写,Luogu,省选,le,区间,DP
From： https://www.cnblogs.com/SoyTony/p/DP_Training_Problems_of_Provincial_Team_Selection_in_Bei