经验总结

  1. 首页 > 生活 > >

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

生活百科

int 数组是不是有那么亿点点大？
那么如何优化代码呢？
注意到上题的代码中 ， 逆序对数枚举的上限为 \(\frac {n \times (n-1)} {2}\) ， 再瞅一眼本题数据范围 ， 最大逆序对数只有 \(1000\)？！
不难想到改成以下代码：
const int N = 1010, mod = 10000;int n, k, f[N][N], s[N ];int main() { n = read(), k = read(); 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 <= min((i * (i - 1)) >> 1, k); j++)s[j] = (s[j - 1] + f[i - 1][j]) % mod;for (int j = 1; j <= min((i * (i - 1)) >> 1, k); j++)f[i][j] = (s[j] + mod - ((j - (i - 1) - 1) < 0 ? 0 : s[j - (i - 1) - 1])) % mod; } printf("%d\n", f[n][k]); return 0;}真好 ， 既优化了空间又优化了时间 。
2. 单调队列优化dpOI-Wiki 传送门
借助单调队列的单调性 ， 及时排除不可能的决策 ， 保持候选集合的高度有效性和秩序性 。
单调队列尤其适合优化决策取值范围的上、下界均单调变化 ， 每个决策在候选集合中插入或删除至多一侧的问题 。
2.1 P1440 求m区间内的最小值2.1.1 题目大意给定一个长度为 \(n\) 的数列 \(a\) ， 对于每个 \(i\) 输出 \(min\{a_{i-m},a_{i-m+1},..,a_{i-1}\}\) 。
2.1.2 数据范围\(1\leq m\leq n\leq 2\times10^6\) ， \(1\leq a_i\leq3\times10^7\) 。
2.1.3 做法好像和单调队列优化dp没什么关系？
此题用于体验单调队列 ， 就不多写了 ， 直接用单调队列模拟操作即可 。
const int N = 2000010;int n, m, s[N], l = 1, r, a[N];int main() { n = read(), m = read(); printf("0\n"); for (int i = 1; i <= n - 1; i++) {a[i] = read();while (r >= l && a[s[r]] > a[i]) r--;s[++r] = i;while (s[r] - s[l] + 1 > m && l <= r) l++;printf("%d\n", a[s[l]]); } return 0;}2.2 P5858 「SWTR-03」Golden Sword2.2.1 题目大意有 \(n\) 个物品 ， 编号 \(1..n\) ， 每个物品有坚固值 \(a_i\) 。
进行 \(n\) 次操作 ， 对于每次操作 ， 执行以下步骤：

  1. 取出不超过 \(s\) 个物品 。
  2. 放入物品 \(i\) 。
其中容器最多容纳 \(w\) 个物品 。
每次操作会产生 \(a_i\times 物品数（包括放入的物品）\) 的贡献 。
求 \(n\) 次操作后总贡献的最大值 。
2.2.2 数据范围\(1\leq s\leq w\leq n\leq5\times10^3\) ， \(|a_i|\leq10^9\) 。
2.2.3 做法设 \(f_{i,j}\) 表示正在执行第 \(i\) 次操作 ， 容器内共有 \(j\) 个物品所能得到的最大贡献值 。
那么 \(f_{i,j}=\max\{f_{i-1,k}+a_i\times j\}\) 。
其中 \(j-1\leq k\leq \min\{w,j-1+s\}\) 。
于是就得到了一个45分做法（long long没开全只有35）
const int N = 5010;const ll INF = 1e18;int n, w, s;ll f[N][N], ans = -INF, a[N];int main() { n = read(), w = read(), s = read(); for (int i = 1; i <= n; i++) a[i] = read(); for (int i = 0; i <= n; i++)for (int j = 0; j <= w; j++)f[i][j] = -INF; f[0][0] = 0; for (int i = 1; i <= n; i++)for (int j = 1; j <= w; j++)for (int k = j - 1; k <= min(w, j - 1 + s); k++)f[i][j] = max(f[i][j], f[i - 1][k] + a[i] * j); for (int i = 0; i <= w; i++) ans = max(ans, f[n][i]); printf("%lld\n", ans); return 0;}（不如先动手写个部分分做法？）
考虑优化 。先把式子变一下：\(f_{i,j}=\max\{f_{i-1,k}\}+a_i\times j\)\((j-1\leq k\leq \min\{w,j-1+s\})\) 。很显然对吧 ， 就是把原来max中重叠的部分提出来而已 。虽然说这么一提好像不能优化什么 ， 你会发现 ， \(\max\{f_{i-1,k}\}\) 好像可以用单调队列优化？！
const int N = 5010;const ll INF = 1e18;int n, w, s;ll f[N][N], ans = -INF, a[N];int ss[N];int main() { n = read(), w = read(), s = read(); for (int i = 1; i <= n; i++) a[i] = read(); for (int i = 0; i <= n; i++)for (int j = 0; j <= w; j++)f[i][j] = -INF; f[0][0] = 0; for (int i = 1; i <= n; i++) {int l = 1, r = 0;ss[++r] = w;for (int j = w; j; j--) {while (f[i - 1][ss[r]] < f[i - 1][j - 1] && r >= l) r--;ss[++r] = j - 1;while ((ss[l] - ss[r] + 1) - 1 > s && l <= r) l++;f[i][j] = f[i - 1][ss[l]] + j * a[i];} } for (int i = 0; i <= w; i++) ans = max(ans, f[n][i]); printf("%lld\n", ans); return 0;}

经验总结扩展阅读


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

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