DP决策优化小结

find函数是寻找分界，calc函数即 \(w(j,i)\)。
一种是判断叉掉次队尾时间快慢，一种是直接比较i和队尾转移到队尾与次队尾分界处谁更优。
明显第二种更快，精度要求更低，也更简单。
要重点注意边界问题。

5.二分栈

没打过，但可以口胡。

还是 1D 问题。
但是这次是后面的决策会被前面赶超。

可以类似维护一个单调栈，每个点存储何时叉掉头上那个点，即决策分界。
那么栈顶就是当前最优决策点。

插入时，先比较i是否优于栈顶，劣则扔掉；优则判断栈顶会不会在叉掉i前被次栈顶叉掉，如果会就一直pop栈顶。

6.广义决策单调性

这已经不是玄妙的范畴了。
还是看cmd的吧，我讲不清楚，而且我也没看懂环上魔法。
cmd的 DP的决策单调性优化总结

7.区间dp运用

参考oiwiki-四边形不等式优化

斜率优化

理解后其实挺模式化。
适用于特殊的 1D 问题，
形如 \(dp[i]=min(dp[j]+f[i]\times g[j]+a[i]+b[j])\)。

1.斜率式

顾名思义，把式子整成斜率形式。

假设当前转移到 i，决策点 \(j_2>j_1\)，且 \(j_2\) 优于 \(j_1\)。
那么 \(dp[j_2]+f[i]\times g[j_2]+a[i]+b[j_2]\leq dp[j_1]+f[i]*g[j_1]+a[i]+b[j_1]\)
转化得 \(f[i]\times (g[j_2]-g[j_1])\leq(dp[j_2]+b[j_2])-(dp[j_1]+b[j_1])\)
令 \(X(j)=g[j]\)，\(Y(j)=dp[j]+b[j]\)。
代入移项得 \(f[i]\leq\dfrac{Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}\)。
这是一个斜率形式。

但是不要高兴得太早，上面默认了 \(X(j_2)-X(j_1)>0\) ，实际上这玩意可能会导致变号。特别是 \(X\) 不具有单调性时，有点令人迷惑。

显而易见的，我们可以通过这个式子决定决策点之间的优劣，并使用单调队列进行维护。而上述式决策点构成的集合在坐标系中表现为上凸；反号则为下凸。
关于这部分的证明，可以看辰星凌的 ，写得非常详细，此处不再赘述。

2.直线式（截距式）

这种方法与形的关系更加密切，更加有助于分析问题。

不对式子做过多变换。
原式整理得 \(-f[i]\times g[j]+(dp[i]-a[i])=dp[j]+b[j]\)，
即形如 \(kx+b=y\) 的形式。

可以看到，\(k=-f[i]<0\) 已经确定，而 \(dp[i]_{min}\) 等效于 \(b_{min}\)。
那么我们的目标是找到合适的点 \((g[j],dp[j]+b[j])\) 使过该点且斜率为 \(k\) 的直线截距最小。

显然这玩意应该去维护一个上凸包，用斜率为 \(k\) 的直线去切。
可以发现其实和斜率式的结果并无区别。

3.问题分析

若询问的 \(k\) 与插入的 \(X\) 均单调，那么是有决策单调性的。可以看到队头一定会在某个 \(k\) 被弹出而对后面没有任何贡献。那么可以维护一个单调队列，随 i 递增不断出队头即可。
时间复杂度为 \(O(n)\)。

若询问的 \(k\) 不单调而插入的 \(X\) 单调，那么不能弹出队头，维护的实际上是个单调栈。对于当前 i 查询最优决策点要使用二分，找到第一个满足斜率条件的位置。

若询问的 \(X\) 不单调，不管 \(k\) 是否单调，我们都只能使用数据结构动态维护凸包或者离线算法维护偏序。可以采用平衡树，李超线段树动态维护，或是 CDQ 离线维护，时间复杂度均为 \(O(nlogn)\)。
平衡树因为凸性的原因可以按照 \(X\) 和相邻两点 \(k\) 来 split，避免二分。
CDQ 可以再用 \(O(logn)\) 维护第三维偏序。

4.细节

大多数题目需要先在队列中插入一个零点。
保持出队时保证出队后队列中还有点，最后一个点不能出（其实也出不了，压根没有斜率）。

边界条件需要重点注意。

凸优化/WQS二分

适用于 2D 的分m段极化问题，形如
\(dp[i][s]=min(dp[j][s-1]+w(j,i))\)

1.答案凸性

假设我们已经算出了分 i 段的答案，\(i\in[1,n]\)。
将 \((i,dp[i])\) 在坐标轴上表示出来。

如果这个点集表示出的图形是一个凸包，显然我们可以二分斜率去切这个凸包，直至切到想要的横坐标 m。
则我们只要能够验证答案凸性，就可以解决该问题。
假设此处已有凸性。

但是我们并没有算出答案，而是需要根据我们的二分的斜率 k 算出答案。
若斜率为 k 的直线经过凸包上一点 j，则有 \(kj+b=dp[j]\)。
转化得 \(b=dp[j]-kj\)。

观察到这等价于将每件物品的价值减去 k 的 1D 问题，或者说每分一段就会有 k 的惩罚。那么就可以采取 1D 方式算出 b，进而用 \(dp[j]=kj+b\) 算出 \(dp[j]\)。

其中 1D 处理过程可以记录每个 \(dp[i]\) 分了多少段，依此决定二分区间。

2.实际问题

关于切k段问题，凸性是可以由决策单调性推导得到的。
这个可以看Itst爷的
原理大概是通过抽屉构造可行解，并证明可行解满足条件，那么最优解一定满足条件。

方向可以通过决策单调性与极小情况得到。此处给出一个简单例子。

利用归纳法证明。
极小情况 \(w(x,x)+w(x+1,x+1)\leq w(x,x+1)\) 已经满足。
设 \(a。
假设已知 \(w(b,c)+w(c+1,d)\leq w(b,d)\)......①
欲证 \(w(a,c)+w(c+1,d)\leq w(a,d)\)......②
由四边形不等式 \(w(a,c)+w(b,d)\leq w(a,d)+w(b,c)\)，
代入 ① 得 \(w(a,c)+w(b,c)+w(c+1,d)\leq w(a,c)+w(b,d)\leq w(a,d)+w(b,c)\)
整理得 \(w(a,c)+w(c+1,d)\leq w(a,d)\)，即 ② 式。