『分治法优化DP』[POI2011]Lightning Conductor

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

给定一个长度为 $n$ 的序列 { a n } \{a_n\} { an?}，对于每个 $i\in [1,n]$ ，求出一个最小的非负整数 $p$ ，使得 $?j\in [1,n]$，都有 $a_j\le a_i+p?\sqrt{|i?j|}$

$1\le n\le 5\times 10^5$，$0\le a_i\le 10^9$ 。

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

如果我们设 $f_i$ 表示当前数字$i$的答案，那么显然有方程：$$f_i=\max (f_j+\sqrt{|i?j|}?f_i)$$
那么我们将方程内的绝对值拆开并分类讨论，则有：$$f_i=\max (f_j+\sqrt{i?j}?f_j)(j\le i)$$
$$f_i=\max (f_j+\sqrt{j?i}?f_j)(i\le j)$$

那么我们就将题目转化为了两个问题，我们通过达标发现：

• 第一个状态转移方程的决策点单调不下降。
• 第二个状态转移方程的决策点单调不上升。

观察到 { f i } \{ f_i \} { fi?}的转移线性无关。我们考虑分治法来优化DP。

函数$\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}(\mathrm{l},\mathrm{r},\mathrm{L},\mathrm{R})$表示我们需要转移$[l,r]$内的状态，其中可选的决策是$[L,R]$。

• 每一次取出中点，找到中点的决策点$p$。
• 递归查找$\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}(\mathrm{l},\mathrm{m}\mathrm{i}\mathrm{d}?1,\mathrm{L},\mathrm{p})$和$\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{c}(\mathrm{m}\mathrm{i}\mathrm{d}+1,\mathrm{r},\mathrm{p},\mathrm{R})$。

这样，我们就优化掉了一重$O(n)$的复杂度，总复杂度为$O(nlogn).$

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h> using namespace std;
const int N = 6e5;int n;
double a[N], f1[N], f2[N];int read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}void Solve1(int l, int r, int ll, int rr)
{
    if (l > r) return;int p = 0, mid = l + r >> 1;double res = 0;for (int i=ll;i<=min(mid,rr);++i){
    double val = a[i] + sqrt(mid - i) - a[mid];if (val > f1[mid]) f1[mid] = val, p = i;}Solve1(l, mid-1, ll, p);Solve1(mid+1, r, p, rr);return;
}void Solve2(int l, int r, int ll, int rr)
{
    if (l > r) return;int p = 0, mid = l + r >> 1;double res = 0;for (int i=max(ll,mid);i<=rr;++i){
    double val = a[i] + sqrt(i - mid) - a[mid];if (val > f2[mid]) f2[mid] = val, p = i;}Solve2(l, mid-1, ll, p);Solve2(mid+1, r, p, rr);return;
}int main(void)
{
    n = read();for (int i=1;i<=n;++i) a[i] = 1.0 * read();Solve1(1, n, 1, n);Solve2(1, n, 1, n);for (int i=1;i<=n;++i) printf("%.0lf\n", ceil(max(f1[i], f2[i])));return 0;
}