随机说话 2

· · 个人记录

设指示函数 w:\mathbb{N}^2 \to \{0,1\}。一个基本的 dp 模型是

f_i \gets f_j, j<i \land w(j,i)=1

计数 dp 就是加法,最优化 dp 就是 chkmax/min。

平方做法一般显然。优化这种式子,本质是维护半在线数据结构,支持插点 (i,f_i),查询 w(j,i)=1 的 f_j 总和 / 最优值。

常见的思路: