动态dp学习笔记

\(noip\)考了，赶紧补一发。

不得不说网上的题解还是不错的ljq的代码吼啊

• 一开始看的博客
• 模板

• 其实我感觉看博客不如看别人优秀的代码来的快

  首先是树链剖分的思想

• 讲一讲自己的感想
• 首先我们为了使得\(f\)带修改，引入了树链剖分套线段树维护矩阵进行\(dp\)。
• 但是这样我们是无法直接维护\(f\)的，因为剖分的思想是重链不会超过\(log\)次划分。
• 假设我们现在可以一次性跳完整个重链，那么问题就变成了是否可以从重链顶跳到上一个重链
• 于是我们引入新数组\(g\)，表示不算当前重链的所有贡献。
• 那么我们只需要维护\(g\)，每次修改就直接把整个重链的\(g\)全部\(\prod\)起来，然后修改父亲的\(f\)。
• 此时我们发现，不是每个地方的\(f\)都是有意义的。
• 首先我们知道每个位置的\(g\)，然后用线段树维护他。
• 维护\(g\)的原因是我们可以通过线段树优化\(dp\)转移使得在\(log\)的时间内得到一段的\(g\)卷积。
• 所以我们只知道每个链顶的\(f\)值，而并不关心每个点的\(f\)。
• 那么问题就简单多了，对于每次修改，我们只需要修改当前点的\(g\)，然后\(\prod\)到链顶的\(f\)，再用当前的\(f\)更新父亲的\(g\)，重复这个操作。
• 实际上我们又给出了\(f\)的新定义，即\(f=\prod g\).
• 总结一下就是：
• 个人认为动态\(dp\)的思想在于整体考虑一整个重链的\(dp\)转移。
• 然后再把这个重链的\(dp\)转移贡献给链顶父亲
• 那么在实际设计状态的时候，形如\(g_{i,j}\)表示\(i\)点不考虑重儿子的\(dp\)值。
• 然后根据状态转移方程一次性考虑一整个重链
• 这样的话，我们在修改操作的时候，就只需要考虑链与链之间的关系了。

• 至此，我们得到了一个\(O(4*q*log^2n)\)的做法。

  但是这样还是不够优秀

• 晚上更。

动态dp学习笔记

原文：https://www.cnblogs.com/Tyher/p/10025513.html