经验总结

  1. 首页 > 生活 > >

dp优化 | 各种dp优化方式例题精选

生活百科

前言本文选题都较为基础 ， 仅用于展示优化方式 ， 如果是要找题单而不是看基础概念 ， 请忽略本文 。
本文包含一些常见的dp优化（“√”表示下文会进行展示 ， 没“√”表示暂时还咕着）：前缀和优化（√）、单调队列优化（√）、斜率优化（√）、四边形不等式优化、数据结构优化……
由于写本文主要是记录蒟蒻的dp优化学习过程 ， 所以可能很不完善 ， 也会有很多错误 (?)。推荐看巨佬的：【学习笔记】动态规划—各种 DP 优化 - 辰星凌
1. 前缀和优化dp进行状态转移时 ， 如果发现需加上前面的一类状态 ， 就可以选择使用数组进行累计操作 ， 以达到降维度的效果 。
1.1 P1521 求逆序对1.1.1 题目大意给出 \(n\) ， \(k\) ， 问 \(1..n\) 的排列中正好有 \(k\) 个逆序对的排列数 。
1.1.2 数据范围\(1 \leq n \leq 100\) ， \(1 \leq k \leq n * (n - 1) / 2\) 。
1.1.3 做法设 \(f_{i, j}\) 表示 \(1..i\) 的全排列中有 \(j\) 个逆序对的排列数 。答案即为 \(f_{n, k}\) 。
考虑在 \(1..(i-1)\) 的排列中加入一个 \(i\) 所能贡献的逆序对数量 。由于 \(i\) 是最大的 ， 故当它被排在第 \(j\) 个时 ， 相应的逆序对数量会增加 \(i - j\) 个 。
不难列出转移式：\(f_{i, j}=\sum_{k = 0}^{min(j, i - 1)}f_{i - 1, j - k}\) 。
其中的 \(k\) 表示新增的逆序对数 。
同时初始化 \(f_{1, 0}=1\) 。
由于此题比较水 ， 所以不优化也能过 。
const int N = 110, mod = 10000;int n, k, f[N][N * N >> 1];int main() { n = read(), k = read(); f[1][0] = 1; for (int i = 2; i <= n; i++)for (int j = 0; j <= (i * (i - 1)) >> 1; j++)for (int k = 0; k <= min(j, i - 1); k++)f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod; printf("%d\n", f[n][k]); return 0;}接下来开始优化 。
现在把上面转移的式子改一下 ， 方便优化：
\(f_{i, j}=\sum_{k = max(0, j - (i - 1))}^jf_{i - 1, k}\) ， 相应的 ， 代码可以改成这样：
for (int i = 2; i <= n; i++)for (int j = 0; j <= (i * (i - 1)) >> 1; j++)for (int k = max(0, j - (i - 1)); k <= j; k++)f[i][j] = (f[i][j] + f[i - 1][k]) % mod;开数组 \(s_{i, j}=\sum_{k = 0}^jf_{i, k}\) ， 那么 \(s_{i, j}=s_{i, j - 1}+f_{i, j}\)。
相应的 ， 转移式变为 \(f_{i, j}=s_{i - 1,j}-s_{i - 1, j - (i - 1) - 1}\) ， 注意边界问题 。
for (int i = 1; i <= n; i++) f[i][0] = s[i][0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= (i * (i - 1)) >> 1; j++)s[i - 1][j] = (s[i - 1][j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= (i * (i - 1)) >> 1; j++)f[i][j] = (s[i - 1][j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[i - 1][j - (i - 1) - 1])) % mod; }注意到 \(s\) 数组的前一维似乎没有什么用处 ， 考虑使用滚动数组继续优化 。
for (int i = 1; i <= n; i++) f[i][0] = 1; s[0] = 1; for (int i = 2; i <= n; i++) {for (int j = 1; j <= (i * (i - 1)) >> 1; j++)s[j] = (s[j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= (i * (i - 1)) >> 1; j++)f[i][j] = (s[j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[j - (i - 1) - 1])) % mod; }1.2 P2513 [HAOI2009]逆序对数列1.2.1 题目大意给出 \(n\) ， \(k\) ， 问 \(1..n\) 的排列中正好有 \(k\) 个逆序对的排列数 。
1.2.2 数据范围\(1 \leq n, k \leq 1000\) 。
1.2.3 做法乍一眼看是不是和上题一模一样 。
如果直接提交上题的代码（改了数据范围） ， 就会得到30分的好成绩 。（最后几个点全部MLE）
稍稍计算一下 ， 就会发现 \(499500000\) 的

经验总结扩展阅读


上一篇：故事 --- Linux和UNIX之间的那些爱恨与情仇

下一篇：男孩变声后的生长规律