信行散记

但行好事，莫问前程

0%

发表于 更新于

dp 优化方法

fi=min⁡i−l<j<i{fj+pj}+pi单调队列优化fi=∑i−l<j<i{fj+pj}+pi前缀和优化fi=min⁡i−l<j<i{fj+pjwi}+pi斜率优化fi=∑1≤j<i{fj+gi−j}+pi分治FFTfi=min⁡⋯…⋱{fj}+piCDQ 分治fi=min⁡j<i{fj+w(j+1,i)}决策单调性f_i = \min_{i - l < j < i} \{f_j + p_j\} + p_i \qquad\text{单调队列优化} \\ f_i = \sum_{i - l < j < i} \{f_j + p_j\} + p_i \qquad\text{前缀和优化} \\ f_i = \min_{i - l < j < i} \{f_j + p_jw_i\} + p_i \qquad\text{斜率优化} \\ f_i = \sum_{1 \le j <i} \{f_j + g_{i - j}\} + p_i \qquad\text{分治FFT} \\ f_i = \min_{\cdots \ldots \ddots} \{f_j\}+ p_i \qquad\text{CDQ 分治} \\ f_i = \min_{j < i}\{f_j + w(j + 1, i)\}\qquad\text{决策单调性}

还有WQS二分凸优化，长链剖分，线段树合并，矩阵优化DDP, 齐次线性递推，生成函数等。

阅读全文 »

发表于 更新于

计数/决策类DP

计数类DP

通常使用 dp[i][j] 表示满足 (i, j) 条件的计数。递推即可

发表于 更新于

区间DP和树形DP

区间DP, 就是以区间作为状态的DP
树形DP, 就是以子树作为状态的DP

区间DP的一般套路
dp[l][r] 表示从l到r的状态值

树形DP的一般套路
dp[u][辅助数] 表示以 u 为根节点的子树，满足条件的状态值。

典型例题: