p9197
P9197 [JOI Open 2016] 摩天大楼
学习:连续端 dp。 目标:最优化 \(F(S) = \sum_{i=1}^{n-1} w(A_{S_i}, A_{S_{i+1}})\),或者说,重排序列以最优化相邻两个元素产生的贡献。 考虑拆开贡献,拆成类似 \(L(a_i) + R(a_{i+1})\) 的形式。连续端 dp 通过以下两个操作 ......
P9197 [JOI Open 2016] 摩天大楼
[传送门](https://www.luogu.com.cn/problem/P9197) 为了规避绝对值,我们可以先将$a_i$从小到大排序 考虑$DP$:假如我们计算到$a_g$,则$f_{i,j,0/1,0/1}$定义为当前阶段有$i$段,这$i$段数全用$a_g$连接的值为$j$,是否有左端 ......
「解题报告」P9197 [JOI Open 2016] 摩天大楼
水个题。 好像是连续段 DP 模板题,但是没怎么做过连续段 DP。 连续段 DP 大致思想就是对排列的计数,可以按照某个顺序依次填入每个数,将当前填的数看做若干连续段,每次考虑合并两个连续段,新建两个连续段或拓展一个连续段,然后就容易对排列进行计数了。 这题有一个绝对值的限制,而我们可以把绝对值按照 ......