DP优化小结

CDQ分治 DP

在很多情况下，我们需要把复杂度为$O(n^2)$的DP优化到$O(nlogn)$。此时我们有几种方式来优化。

矩阵优化

又名矩阵快速幂。
特点
1.转移要选取的决策较少。（一般在常数级别）
2.转移的步骤很多。（一般是$10^{10}$以上的级别）
3.每一步的转移方程一样。（和递推类似）
(看到$n\leq 10^{18}$之流只会这么搞）
如设$m$为每次转移决策数，
时间复杂度$O(m^3logn)$

矩阵设定

• $f(n)=f(n-1)+f(n-2)$(只有两个决策，每次转移都一样）
  初始矩阵
  $A=[f(n-1),f(n)]$
  目标矩阵
  $B=[f(n),f(n-1)+f(n)]$
  转移矩阵
  $T=\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}$
  显然，$B_n=A_1*T^{n-1}$。

• $f(n)=f(n-2)+f(n-1)+1$
  初始矩阵
  $A=[f(n-1),f(n-1)+f(n)+1,1]$
  目标矩阵
  $B=[f(n),f(n-1)+f(n)+1,1]$
  转移矩阵
  $T=\begin{matrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}$

单调队列优化

• 对于DP方程$dp[i]=min(dp[j]+f(j))(0<j<i)$
  用一个变量维护$(0,i)$中$dp[j]+f(j)$的最小值即可
• 对于DP方程$dp[i]=min(dp[j]+f(j))(i-m<j<i)$
  用一个单调队列维护$(i-m,j)$中$dp[j]+f(j)$的最小值

斜率优化

基本形式

$dp[i]=min(dp[j]+f(i,j))$
即方程表达式中含有两个未知量。

思想

我们可以先化一下DP方程式。
最终形式为$y=kx+b+dp[i]$

• 拆括号
• 去掉只与$i$和已知量相关的部分（最后再加回来）
• $y$为$dp[j]$
• $kx$为分别与$i,j$直接相关量的相乘部分
• $j$为只与$j$相关量
  以[SDOI2012]任务安排为例
  裸dp方程式为$dp[i]=dp[j]+(f[n]-f[j])*(t[i]-t[j]+s)$
• 拆括号$dp[i]=dp[j]+f[n]*t[i]+f[n]*f[j]+f[n]*s-f[j]*t[i]+f[j]*t[j]-f[j]*s$
• 去$i$
  $dp[i]=dp[j]+f[n]*f[j]-f[j]*t[i]+f[j]*t[j]-f[j]*s$
• 移项
  $dp[j]=t[i]*f[j]+(f[n]*f[j]+f[j]*t[j]-f[j]*s)+dp[i]$
  显然，只有$i$会影响当前$dp[j]$的最优性，如果$t[i]$单调递增，我们就可以维护一个单调栈。
  取最大值，就让斜率递增
  取最小值，就让斜率递减
  最后我们取队首元素即可。

CDQ分治/平衡树优化DP

如果我们拆完式子后，发现斜率不递增，上面方法就失效了。
我们于是需要使用分治方法来优化复杂度（在这里为CDQ分治）。

• 开始初始化$x$,$k$。
• 以$k$为标准从小到大排序。
• CDQ分治（l为DP出发点，r为DP终结点）