比如一些 $(i, j)$ 可以从 $(s, j)(1 \leq s \lt i)$ 和 $(i, s)(1 \leq s \lt j)$ 中任一转移来的题目。
by FGgirl @ 2023-10-11 17:15:35
哦这个是不是也可以分治 但是我觉得这种奇怪题目封装不容易写寄
by FGgirl @ 2023-10-11 17:17:13
分治怎么做一维dp的转移。
by Graygoo @ 2023-10-11 17:43:13
那些要由之前 DP 值推到现在 DP 值的应该都不能用吧
其实只有少数题才能分治（？
by Jsxts_ @ 2023-10-11 19:31:07
@[fjy666](/user/366338) 离线的东西才可以分治，比如 $f_{i,j}$ 只能从 $f_{i-1,k}$ 转移而来，即已经知道了上一层的所有 DP 值。
感觉分治主要是用来解决代价不好计算的问题的。
by WrongAnswer_90 @ 2023-11-16 09:04:00
@[fjy666](/user/366338) 还是二分栈更通用吧，比如邮局分治做法可以 wqs 二分转成单调栈做到更优秀的复杂度
by WrongAnswer_90 @ 2023-11-16 09:06:10
@[fjy666](/user/366338) 但是这题确实可以。。只有一层
by WrongAnswer_90 @ 2023-11-16 09:21:59
是。
by fjy666 @ 2023-11-23 22:16:00
@[Graygoo](/user/535714) 实际上这题压根就不是dp，状态和转移都没有，不符合 dp 的定义。
by XHY20180718 @ 2024-01-18 20:46:34
@[WrongAnswer_90](/user/134510) 代价不好计算通常需要移动之前已经计算过的代价把，分治不是难点，只是辅助？
但是这道题没有状态，可以直接分治，用二分栈也可以，但是常数很大。
感觉知道决策单调性是啥后，又比较了解分治的思想就能做这题，不知道为啥评紫？
by XHY20180718 @ 2024-01-18 20:55:08