DDP

· · 个人记录

浅谈动态DP

又称 DDP，主要用于解决一类序列（树上）的 dp 问题 。

引入 ？考虑最大子段和问题，扔到区间上怎么去做（其实就是小白逛公园）

维护区间信息，较为普遍的是线段树，其维护信息的核心在于其结合律，而交换律并不是必须的。

固然，我们可以仿照那题一般做法地去维护左右最大子段和，区间和，区间最大子段和。但是我们希望得到一个泛用性更广的做法。

为什么可以如此维护？因为合并时的结合律！

既然如此，我们如果把 dp 的转移过程变成一个具有结合律的过程，不就可以在线段树上维护了吗？

考虑一般序列上怎么解决这个问题。

设 f_i 表示到 i 为止时候的最大字段和，每个点选取的贡献是 v_i ，那么有转移方程 f_i = max(f_{i-1}+v_i,f_{i-1}) 。答案对于 f_i 取 max 即可

多个信息，结合律，转移维护，考虑矩阵乘法。

but 我们知道一般的矩阵乘法形如 \displaystyle (AB)_{i,j} = \sum_{k} A_{i,k}B_{k,j}

好像，和上面的柿子相比，似乎还差一个 max？

考虑定义一个广义的矩阵乘法 \displaystyle (AB)_{i,j} =\max_{k} A_{i,k}+B_{k,j}

现在，我们要考虑我们定义的这个新运算是否满足结合性，不妨设上述运算可写成 A * B 即考虑证明 (A*B)*C = A*(B*C)

我们知道，一般的矩阵乘法是具有结合律的（关于证明，可借助《具体数学》多重和式一章中 2.27部分，此处不再展开），它依赖加法的结合律，乘法结合律以及乘法对加法的分配律。而 max 对加法有着类似的性质，因而这种运算是满足结合律的。（似乎可以借助复合函数的结合性证明但是我不会）

言归正传，把信息打包成矩阵来处理，利用线段树以及信息结合律维护 dp 转移过程，这就是DDP的核心思想。

至于上面那个问题？ 考虑额外记录一个 ans_i 表示到 i 为止时候的答案，有ans_i = max(ans_{i-1},f_i)，正常构造转移矩阵维护一个区间前缀积就做完了。

我们观察一下这种 dp 的特点：

  1. 需求信息量较小，因为矩阵乘法的复杂度是 O(v^3) (此处默认矩阵长宽相等而 v 为矩阵的边长)，时间开销较大。
  2. 需要转移的信息都可以由已知推得（你的转移矩阵里面需要都是已知量）

考虑类似的 dp 问题丢到树上怎么去做（前置知识 LCT，树剖等可维护树上区间操作的数据结构）

例题

P5558 心上秋

简要题意：树上维护最长不下降子序列。

倘若类似序列做法，用树状数组维护转移点，明显行不通。一方面，每个位置的转移点可能受路径的影响，另一方面，我们必须知道某点之前所有路径的 dp 值才能转移，这样需要的信息太多，矩阵乘法时间开销过大。

观察到值域只有 1 到 5，这启示我们用一个和值域有关的状态维护。得到转移方程之后构造转移矩阵即可。详见 P5558。

与序列维护过程中不同的地方？由于矩阵乘法并不满足交换律，所以转移过程可以看作是一个有向线段从 S 走到 T。

而由于树剖时我们维护链的信息是借助 dfn 序由链首到链尾（按照正常左区间与右区间合并的写法），所以对于 S 和 T 不在一条重链上的情况，直接合并信息是错误的。

如下图所示，假如我们现在要维护从 8 \rightarrow 6 的路径信息 那么按照正常树剖维护线段树的写法，蓝色部分是我们按照正常写法维护的信息，红色部分是我们实际上需要的信息（包含方向）。

那么从 8 \rightarrow 1 这条链上维护的信息和我们所需要信息方向是完全相反的，如上文所述，矩阵乘法并不满足交换律，因此这样直接去做会是错误的。

如何解决呢，我们只需要类似地在线段树上维护一个从右往左地区间来进行合并就好了。类似于这样，注意，此处初始矩阵是相同的。

void up(int p)
{
    lft[p] = lft[lp] * lft[rp];
    rit[p] = rit[rp] * rit[lp]; 
}

不过，还有一个问题是，树剖获取链信息的时候是从下往上跳的获取的，那么在维护树剖的过程中还要注意先前的矩阵信息与后来的矩阵信息合并时的先后顺序。

具体地，在代码实现中，我是这样实现的

while(top[S]^top[T])
{
    if(dep[top[S]] > dep[top[T]])
    {
//      cout << "S:" << S << "--->" << top[S] << "\n";
        resS = resS * query_rit(1,1,n,dfn[top[S]],dfn[S]);
        S = anc[top[S]]; 
    }
    else 
    {
        resT = query_lft(1,1,n,dfn[top[T]],dfn[T]) * resT;
        T = anc[top[T]];
    }
}
if(dep[S] > dep[T])
{
    resS = resS * query_rit(1,1,n,dfn[T] + 1,dfn[S]); 
}
else 
{
    resT = query_lft(1,1,n,dfn[S] + 1,dfn[T]) * resT;
}

这里不采用一般地交换x，y也是因为其交换律的问题。如此，你已经可以解决一般地非修改的DDP了。 至于带修改的嘛，再咕咕一下（其实做了一些但还没整理完