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\) 次操作,对于每次操作,执行以下步骤:
- 取出不超过 \(s\) 个物品 。
- 放入物品 \(i\) 。
每次操作会产生 \(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;}
3. 斜率优化dpOI-Wiki 传送门3.1 P3195 [HNOI2008]玩具装箱3.1.1 题目大意有 \(n\) 件物品,第 \(i\) 件物品压缩后占用 \(C_i\) 的长度 。
现需把这些物品压缩进一些容器里,制作一个容器的花费为 \((x-L)^2\),其中 \(x\) 表示容器长度 。
每个容器中的物品编号需要是连续的,而将编号 \(i\) 到 \(j\) 的所有物品放在一个容器中,占用的空间 \(x=j-i+\sum_{k=i}^j C_k\) 。
求压缩完所有物品所需的总花费的最小值 。
3.1.2 数据范围\(1\leq n\leq 5\times10^4\),\(1\leq L\leq10^7\),\(1\leq C_i\leq10^7\) 。
3.1.3 做法设 \(f_i\) 表示压缩到第 \(i\) 件物品所需的最小花费,不难列出转移方程:
\(f_i=\min\{f_j+(i-j-1+\sum_{k=j+1}^i c_k-L)^2\}\)
令 \(sum_i=\sum_{k=1}^i c_k\),原式可转化为:
\(f_i=\min\{f_j+(i-j-1+sum_i-sum_j-L)^2\}\) 。
移项得:
\(f_i=\min\{f_j+((i+sum_i)-(j+sum_j)-(L+1))^2\}\)
令 \(pre_i=sum_i+i\),原式可转化为:
\(f_i=\min\{f_j+(pre_i-pre_j-(L+1))^2\}\)
把式子展开再合并:
\(f_i=\min\{f_j+pre_i^2-pre_i\times pre_j-(L+1)\times pre_i-pre_i\times pre_j+pre_j^2+(L+1)\times pre_j-(L+1)\times pre_i+(L+1)\times pre_j+(L+1)^2\}\)
\(f_i=\min\{f_j+pre_i^2+pre_j^2-2\times pre_i\times pre_j-2\times(L+1)\times(pre_i-pre_j)+(L+1)^2\}\)
\(f_i=\min\{f_j+(pre_i-pre_j)^2-2\times(pre_i-pre_j)\times(L+1)+(L+1)^2\}\)
\(f_i=\min\{f_j+(pre_i-pre_j-(L+1))^2\}\)
\(f_i=\min\{f_j+((pre_i-(L+1))-pre_j)^2\}\)
\(f_i=\min\{f_j+(pre_i-(L+1))^2-2\times(pre_i-(L+1))\times pre_j+pre_j^2\}\)
\(f_i-(pre_i-(L+1))^2=\min\{f_j+pre_j^2-2\times(pre_i-(L+1))\times pre_j\}\)
令:
\(\begin{eqnarray}\begin{cases}b_i=f_i-(pre_i-(L+1)^2)\\x_j=pre_j\\y_j=f_j+pre_j^2\\k_i=2\times(pre_i-(L+1))\end{cases}\end{eqnarray}\)
推荐阅读
- 梦幻西游搬砖赚钱方式(梦幻西游搬砖如何月入3000)
- 灵域境界等级划分_灵域各种等级势力介绍
- 基于PL022 SPI 控制器 海思3516系列芯片SPI速率慢问题深入分析与优化
- 我的世界创造模式怎么骑马,骑马方式详解(在我的世界里面怎么教我们骑马)
- 云计算_OpenStack
- zip怎么设置默认打开方式(怎么更换zip打开方式)
- Vue3 SFC 和 TSX 方式调用子组件中的函数
- 九重试炼免广告卷获取方式是什么
- 怎么在线预览.doc,.docx,.ofd,.pdf,.wps,.cad文件以及Office文档的在线解析方式。
- 京东云TiDB SQL优化的最佳实践