四边形不等式优化

对于问题 $i$，最优决策集合未必是一个区间．决策单调性实际可以定义在最优决策集合上．对于集合 $A$ 和 $B$，可以定义 $A \leq B$ 当且仅当对于任意 $a\in A$ 和 $b\in B$，成立 $\min\{a,b\}\in A$ 和 $\max\{a,b\}\in B$．这蕴含最小（最大）最优决策点的单调性，即此处采取的定义．本文关于最小最优决策点叙述的结论，同样适用于最大最优决策点．但是，存在情形，某更大问题的最小最优决策严格小于另一更小问题的最大最优决策，亦即可能对某些 $i_1 < i_2$ 成立 $\mathop{\mathrm{optmax}}(i_1) > \mathop{\mathrm{optmin}}(i_2)$，所以在书写代码时，应保证总是求得最小或最大的最优决策点．

另一方面，拥有相同最小最优决策的问题构成一个区间．这一区间，作为最小最优决策的函数，应严格递增．亦即，给定 $j_1 = \operatorname{opt}(i_1)$，$j_2 = \operatorname{opt}(i_2)$，如果 $j_1 < j_2$，那么必然有 $i_1 < i_2$．换言之，如果决策 $j_1 < j_2$ 能够成为最小最优决策的问题区间分别是 $[l_{j_1},r_{j_1}]$ 和 $[l_{j_2},r_{j_2}]$，那么必然有 $r_{j_1} < l_{j_2}$．

若 $w$ 满足四边形不等式，则问题 (1) 满足决策单调性．

要证明这一点，可采用反证法．假设对某些 $c < d$，成立 $a = \operatorname{opt}(d) < \operatorname{opt}(c) = b$．此时有 $a < b \leq c < d$．根据最优化条件，$w(a,d) \leq w(b,d)$ 且 $w(b,c) < w(a,c)$，于是，$w(a,d) - w(b,d) \leq 0 < w(a,c) - w(b,c)$，这与四边形不等式矛盾．

设 $\operatorname{opt}_k(i)$ 是仅考虑 $[1,k]$ 中的决策时，问题 $i$ 的最小最优决策．如果 $w$ 满足四边形不等式，那么对于任意 $i_1 < i_2$，必然成立 $\operatorname{opt}_k(i_1) \leq \operatorname{opt}_k(i_2)$．

设 $M$ 是充分大的正实数．函数 $w'(j,i) = w(j,i) + M[j > k]$ 仍然满足四边形不等式，其中，$[\cdot]$ 是 Iverson 括号．考虑以 $w'$ 为成本函数的辅助 DP．在辅助 DP 中，对于任何问题 $i$，决策 $j > k$ 都不可能是最小最优的，即 $\operatorname{opt}'(i) = \operatorname{opt}'_k(i) = \operatorname{opt}_k(i)$．对辅助 DP 应用定理 1 就得到本推论．

显然，经过不等式变形，我们可以得到待求整数 $f_i = \max_{j}\{a_j+\sqrt{|i-j|}-a_i\}$．不妨先考虑 $j \leq i$ 的情况（另外一种情况类似），此时我们可以得到状态转移方程：

根据 $-\sqrt{x}$ 的凸性，我们很容易得出（后文将详细描述）函数 $w(l, r) = -a_l - \sqrt{r-l} + a_r$ 满足四边形不等式，因此套用上述的算法便可在 $O(n\log n)$ 的时间内解决此题了．

#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#define all \
  for (auto i : {&q, &l, &r}) (*i)
using namespace std;
int n, a[500009], ans[500009];
deque<int> q, l, r;

double f(int i, int j) { return a[i] + sqrtl(j - i); }

void work() {
  all.clear();
  for (int i = 0; i < n; ++i) {
    if (q.size() && r.front() < i) all.pop_front();  // 队首出队
    if (q.size()) l.front() = i;
    for (; q.size() && f(q.back(), l.back()) <= f(i, l.back());)  // 队尾出队
      all.pop_back();
    if (q.empty())  // 入队
      q.emplace_back(i), l.emplace_back(i), r.emplace_back(n);
    else if (f(q.back(), n) < f(i, n)) {
      int ll = l.back(), rr = n, mid;
      for (; ll <= rr;) {
        mid = (ll + rr) >> 1;
        if (f(q.back(), mid) < f(i, mid))
          rr = mid - 1;
        else
          ll = mid + 1;
      }
      r.back() = rr;
      q.emplace_back(i), l.emplace_back(ll), r.emplace_back(n);
    }
    ans[i] = max(ans[i], (int)(ceil(f(q.front(), i))) - a[i]);
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; cin >> a[i++]);
  work();
  reverse(a, a + n);
  reverse(ans, ans + n);
  work();
  reverse(ans, ans + n);
  for (int i = 0; i < n; cout << ans[i++] << '\n');
}

只需要证明游标移动的总次数是 $O(n\log n)$ 的．设 $A$ 和 $B$ 分别为步骤 1 和 3 对应的游标．实际上可以保证：在求解区间 $(l,r]$ 的问题之前，游标 $A$ 处于位置 $(\operatorname{opt}(l),l)$，游标 $B$ 处于位置 $(l,l)$；而在这之后，游标 $A$ 处于位置 $(\operatorname{opt}(r),r)$，游标 $B$ 处于位置 $(r,r)$．

考虑构造如下游标移动规则．步骤 1 中，可以令游标 $A$ 沿着路径

移动．此时，游标 $A$ 和 $B$ 均处于求解区间 $(l,\textit{mid}]$ 的问题之前的规定位置上．步骤 2 中，按规定，游标 $A$ 将移动到 $(\operatorname{opt}(\textit{mid}),\textit{mid})$，游标 $B$ 将移动到 $(\textit{mid},\textit{mid})$．步骤 3 中，可以令游标 $B$ 沿着路径

移动．此时，游标 $A$ 和 $B$ 均处于求解区间 $(\textit{mid},r]$ 的问题之前的规定位置上．步骤 4 中，按规定，游标 $A$ 将移动到 $(\operatorname{opt}(r),r)$，游标 $B$ 将移动到 $(r,r)$．两个游标均在结束求解区间 $(l,r]$ 的问题的规定位置上．因此，这一移动规则符合上述规定．而且，该移动规则足以完成步骤 1 和 3 中的所有计算．直接计算该规则中游标的移动次数可知，步骤 1 需要

次移动，步骤 3 需要

次移动．将这些移动次数对递归树中的所有结点求和，利用同一层中的所有 $[l,r]$ 和 $[\operatorname{opt}(l),\operatorname{opt}_l(r)]$ 至多只在端点处重合这一性质，就可以说明总的移动次数是 $O(n\log n)$ 的．

由于上述移动规则比起实际计算时游标的移动设置了更多的途径点，所以游标的实际移动次数不会超过该规则下移动次数的估计．因此，游标的实际移动次数也是 $O(n\log n)$ 的．

若 $w$ 满足四边形不等式，则对于问题 (2) 成立 $\operatorname{opt}(k-1,i) \leq \operatorname{opt}(k,i) \leq \operatorname{opt}(k,i+1)$．

第二个不等式只是第 $k$ 层的决策单调性．关键在于第一个不等式．

下证 $\operatorname{opt}(k,i) \leq \operatorname{opt}(k+1,i)$．假设有如下两个区间 $[1,i]$ 的分划（逆序标号）：$[a_{k},d_{k}],\cdots,[a_1,d_1]$ 和 $[b_{k+1},c_{k+1}],\cdots,[b_1,c_1]$．其中，每个区间的左端点都是其右端点处对应问题的最小最优决策；同样地，从右向左考虑所有可能的分划，右端点也是左端点对应问题的最小最优决策．例如，$d_j$ 和 $c_j$ 分别是将 $[a_j,i]$ 和 $[b_j,i]$ 分成 $j$ 段左起第一个区间右端点的最小最优决策．根据决策单调性，如果 $a_{j-1} > b_{j-1}$，亦即 $d_j > c_j$，那么必然有 $a_j > b_j$．由此，如果所证不成立，则有 $a_1 > b_1$．进而可以归纳地证明 $a_{k} > b_{k}$．这显然与所设矛盾．由此得证．

第一个不等式可以另证如下．同样考虑上面证明中的两个分划．如果所证命题不成立，则有 $a_1 > b_1$，但是由于有 $a_{k} < b_{k}$，我们可以找到最小的 $j>1$ 使得 $a_j \leq b_j$．进而，此时有 $a_{j-1} > b_{j-1}$，故 $d_j>c_j$．我们找到了一组区间满足 $a_j \leq b_j \leq c_j < d_j$．考虑将这两个分拆重新组合的结果．考虑分拆 $[b_{k+1},c_{k+1}],\cdots,[b_{j+1},c_{j+1}],[b_j,d_j],[a_{j-1},d_{j-1}],\cdots,[a_1,d_1]$，共 $(k+1)$ 段，于是由前设的最优性可推知，

同样地，考虑分拆 $[a_{k},d_{k}],\cdots,[a_{j+1},d_{j+1}],[a_j,c_j],[b_{j-1},c_{j-1}],\cdots,[b_1,c_1]$，共 $k$ 段，则有

此时，不等号是严格的，因为 $a_1 > b_1$，但是按假设，$a_1$ 是所有 $k$ 段分拆最末一段的左端点中最小最优的．两个不等式条件相加，得到 $w(b_j,c_j) + w(a_j,d_j) < w(b_j,d_j) + w(a_j,c_j)$，这有悖于四边形不等式．故而原结论得证．

若 $w$ 满足四边形不等式，则问题 (2) 的最优解 $g(k):=f(n,k)$ 是关于 $k$ 的凸函数．

下证 $g(k-1) + g(k+1) \ge 2g(k)$．为此，考虑长度为 $(k-1)$ 段和 $(k+1)$ 段的最优分划，分别是 $[a_1,d_1],\cdots,[a_{k-1},d_{k-1}]$ 和 $[b_1,c_1],\cdots,[b_{k+1},c_{k+1}]$．取最小的 $1 \leq j \leq k-1$ 使得 $c_{j+1} \leq d_j$，其存在性可由 $c_{k} < n = d_{k-1}$ 推知．根据其最小性得知，$b_{j+1} > a_j$．所以，$a_j < b_{j+1} \leq c_{j+1} \leq d_j$．与上文类似，交换两个现有分拆的后半段，可以得到如下两个区间分拆：

两个所得区间都是 $k$ 段的，所以由最优性条件可知

这里第二个不等式正是四边形不等式．所求凸性由此得证．

每个村庄有其最近的邮局，那么每个邮局也有其管辖的村庄，易知这是一个区间．

考虑把这 $n$ 个村庄分成 $m$ 个区间，再在每个区间中决出一个邮局．

根据数学知识，对于区间 $[i,j]$，邮局应该建在第 $\left\lfloor\dfrac{i+j}2\right\rfloor$ 个村庄处．使用前缀和容易算出 $w(i,j)$．

问题转化为限制区间个数的区间分拆问题．可以证明，$w$ 函数满足四边形不等式．直接应用上述优化方法即可．

#include <iostream>
constexpr int N = 3009;
constexpr int M = 309;
using namespace std;
int n, m, a[N], s[N], g[M][N], p[M][N];

int f(int i, int j) {
  int k = (i + j) >> 1;
  return a[k] * (k - i + 1) - (s[k] - s[i - 1]) + (s[j] - s[k]) -
         a[k] * (j - k);
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; cin >> a[i], s[i] = s[i - 1] + a[i], ++i);
  for (int i = 1; i <= n; ++i) g[0][i] = 1 << 30, p[m + 1][i] = i;
  for (int i = 1; i <= m; ++i) p[i][0] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = m; j; --j) {
      g[j][i] = 1 << 30;
      for (int k = p[j][i - 1]; k <= p[j + 1][i]; ++k) {
        int tmp = g[j - 1][k - 1] + f(k, i);
        if (tmp < g[j][i]) g[j][i] = tmp, p[j][i] = k;
      }
    }
  cout << g[m][n];
}

#include <deque>
#include <iostream>
#define all \
  for (auto i : {&q, &l, &r}) (*i)
using namespace std;
long long n, m, a[500009], s[500009], u, v, w, sum[500009], cnt[500009];
deque<int> q, l, r;

long long f(int i, int j) {
  int k = (i + j) >> 1;
  return sum[i - 1] + v + a[k] * (k - i + 1) - (s[k] - s[i - 1]) +
         (s[j] - s[k]) - a[k] * (j - k);
}

void work() {
  all.clear();
  for (int i = 1; i <= n; ++i) {
    if (q.size() && r.front() < i) all.pop_front();  // 队首出队
    if (q.size()) l.front() = i;
    for (; q.size() && f(q.back(), l.back()) >= f(i, l.back());)  // 队尾出队
      all.pop_back();
    if (q.empty())  // 入队
      q.emplace_back(i), l.emplace_back(i), r.emplace_back((int)n);
    else if (f(q.back(), n) >= f(i, n)) {
      int ll = l.back(), rr = n, mid;
      for (; ll <= rr;) {
        mid = (ll + rr) >> 1;
        if (f(q.back(), mid) >= f(i, mid))
          rr = mid - 1;
        else
          ll = mid + 1;
      }
      r.back() = rr;
      q.emplace_back(i), l.emplace_back(ll), r.emplace_back((int)n);
    }
    sum[i] = f(q.front(), i);
    cnt[i] = cnt[q.front() - 1] + 1;
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; cin >> a[i], s[i] = s[i - 1] + a[i], ++i);
  for (w = 2e12; u <= w;) {  // wqs二分
    v = (u + w) >> 1;
    work();
    if (cnt[n] < m)
      w = v - 1;
    else
      u = v + 1;
  }
  v = w;
  work();
  cout << sum[n] - m * v;
}

若 $w$ 满足区间包含单调性和四边形不等式，则状态 $f(j,i)$ 满足四边形不等式．

不妨设 $a \leq b \leq c \leq d$．下证 $f(a,d) + f(b,c) \geq f(a,c) + f(b,d)$．考虑依 $d-a$ 归纳．当 $a=b$ 或 $c=d$ 时，所求即一等式．对于一般的情形，根据 $d'=\operatorname{opt}(a,d)$ 的位置分类讨论．

第一种情况，$c \leq d'$ 或 $d' < b$，即 $[b,c]$ 包含于 $[a,d']$ 或 $[d'+1,d]$ 之中．

不妨假设 $c \leq d'$，另一种情形同理．此时有

这里，第一个不等式来自于归纳假设 $f(a,c) + f(b,d') \leq f(a,d') + f(b,c)$，第二个不等式来自于区间包含单调性 $w(b,d) \leq w(a,d)$，第三个不等式来自于最优性条件 $f(b,d) \leq f(b,d') + f(d'+1,d) + w(b,d)$．

第二种情况，$b \leq d' < c$，即 $d'$ 位于 $[b,c]$ 之中．此时，考虑 $c'=\operatorname{opt}(b,c)$ 的位置．

不妨假设 $c' \leq d'$，即 $[b,c']$ 包含于 $[a,d']$ 之中，另一种情形同理．此时有

这里，第一个不等式来自于归纳假设 $f(a,c') + f(b,d') \leq f(a,d') + f(b,c')$，第二个不等式来自于四边形不等式 $w(a,c) + w(b,d) \leq w(a,d) + w(b,c)$，第三个不等式来自于 $f(a,c)$ 和 $f(b,d)$ 的最优性条件．

若 $w$ 满足区间包含单调性和四边形不等式，则问题 (3) 中最小最优决策 $\operatorname{opt}(j,i)$ 满足

引理 1 已经证得 $f(j,i)$ 满足四边形不等式，所以目标函数 $f(j,k) + f(k+1,i) + w(j,i)$ 对于给定 $j$ 作为 $(k,i)$ 的函数满足四边形不等式，所以由定理 1 有，$\operatorname{opt}(j,i-1) \leq \operatorname{opt}(j,i)$．注意，不同时含有 $(k,i)$ 的项并不影响四边形不等式成立．类似地，它对于给定 $i$ 作为 $(k,j)$ 的函数也满足四边形不等式，所以 $\operatorname{opt}(j,i) \leq \operatorname{opt}(j+1,i)$．即得所证．