对平移类dp用数据结构优化：ZR2617

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132240791

http://zhengruioi.com/problem/2617

对于此类dp式子：

$$dp_{i,j}=\sum dp_{k,j-w(k,i)}$$

暴力计算为 $O(n^3)$ ，但如果 $w(j,i)$ 在 $w(j,i-1)$ 的基础上变化数量不大（或者变化是个连续区间），就可以拿个数据结构来维护

本质是拿线段树来实现区间平移

实现过程可以拿个标记永久化

在从小到大枚举 $i$ 时，根节点维护当前dp值

---

大胆猜测，此类问题也可做，等我长大回来看

$$dp_{i,j}=\sum (dp_{k,j-w(k,i)}+v(k,i))$$