RainAir
My OI Blog
RainAir
决策单调性优化

写一些简单的 1D/1D 的决策单调性优化…

这种决策单调性优化的过程:列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分

我们以一些例题为例:

[ZROI普转提]Bead

题目链接

注:该题有权限,看不到的就看下一题。

这一题我们推出朴素的状态转移方程:

设 $f[i][k]$ 表示前 $i$ 个数中分成 $k$ 段的最小价值,转移为 $ f[i][k] = min{f[j-1][k-1] + w[j][i]} $,其中 $w[i][j]$ 表示 $i$ 到 $j$ 的价值。

显然 $ w[i][j] $ 可以通过维护 $cnt$ 数组 $N^2$ 求。

我们打表发现 $w$ 是递增的,说明该方程具有决策单调性。

决策单调性有一种较为简单的类似于整体二分的做法就是目前计算 $f[l\cdots r]$ 并且已知它们的决策都在 $[L, R]$ 中,每次暴力计算 $ f[mid] $ 即可。

只需要全局开两个指针 $i,j$ 和一个数组在每次计算 $ f[mid] $ 的时候移动过去并且维护 $cnt$ 即可。

复杂度 $O(nklog_2n)$.

## [NOI2009]诗人小G

题目链接

这一题我们可以轻松的推出朴素的状态转移方程:

设 $f[i]$ 表示前 $ i $ 个句子的最小不协调度,那么 $ f[i] = min{f[j] + |sum[j]-sum[i-1]-L-1|^P} $

我们随意的打个表,发现后面的那一项是递增的。(其实我也不会证明 qaq)

也就是说:我们在转移的时候,不需要考虑较大的状态,从小的状态转移过来。

这个显然可以用单调队列维护。

具体的说,每次我们计算出来的 $ f[i] $,假设它可以用来更新 $ f[j] $ ,那么对于 $j$ 及其以后的状态,都不用考虑 $1 \cdots i-1$ 的状态来转移了。那么我们要做的就是每次我们计算出 $ f[i] $ ,我们找到一个 $f[j]$ ,满足由 $i$ 转移到 $j$ 比$1\cdots i-1$ 更优。由于决策的单调性,可以二分来查找 $j$。最后用单调队列来保存一下决策即可。

代码

~~输出真毒瘤~~

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/84
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

决策单调性优化
写一些简单的 1D/1D 的决策单调性优化... 这种决策单调性优化的过程:列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分 我们以一些例题为例: [ZROI普转提]Bead 题目链接 …
扫描二维码继续阅读
2018-09-01
标签
近期评论