四边形不等式优化

形如以下转移方程：

$$dp[l][r]=min(dp[l][k]=dp[k+1][r])+w(l,r)$$

$w(l,r)$ 需满足的条件：

• 区间包含单调性：若 $l\le l^{\prime }\le r^{\prime }\le r$，则 $w(l^{\prime },r^{\prime })\le w(l,r)$。
• 四边形不等式：若 $l\le l^{\prime }\le r^{\prime }\le r$，则 $w(l,r^{\prime })+2(l^{\prime },r)\le w(l,r)+w(l^{\prime },r^{\prime })$

结论：

• $dp[l][r]$ 也满足四边形不等式。
• 假设 $m[l][r]$ 为 $dp[l][r]$ 的最优决策点，那么 $m[l][r-1]<=m[l][r]<=m[l+1][r]$。

只需要记录 $m[l][r-1$ 和 $m[l+1][r]$，可以优化掉一维循环。

考场上可以直接打表记录 $m_{i,j}$ 后验证单调性

满足四边形不等式的函数类：

性质 1：若函数 $w_1(j,i)$ 和 $w_2(j,i)$ 均满足四边形不等式（或区间包含单调性），则对于任意 $c_1,c_2\ge 0$，函数 $c_1{w}_1+c_2{w}_2$ 也满足四边形不等式（或区间包含单调性）。

性质 2：若存在函数 $f(x)$ 和 $g(x)$ 使得 $w(j,i)=f(j)-g(i)$，则函数 $w$ 满足四边形恒等式。当函数 $f$ 和 $g$ 单调增加时，函数 $w$ 还满足区间包含单调性。

性质 3：设 $h(x)$ 是一个单调增加的凸函数，若函数 $w(j,i)$ 满足四边形不等式并且对区间包含关系具有单调性，则复合函数 $h(w(j,i))$ 也满足四边形不等式和区间包含单调性。

性质 4：设 $h(x)$ 是一个凸函数，若函数 $w(j,i)$ 满足四边形恒等式并且对区间包含关系具有单调性，则复合函数 $h(w(j,i))$ 也满足四边形不等式。

首先需要澄清一点，凸函数（Convex Function）的定义在国内教材中有分歧，此处的凸函数指的是下凸函数，即（可微时）一阶导数单调增加的函数。

CF321E：

void solve() {
  int n, m;
  io.read(n);
  io.read(m);
  vector<vector<int>> a(n + 10, vector<int>(n + 10));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      io.read(a[i][j]);
    }
  }
  auto p = a;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
    }
  }
  auto get_sum = [&](int l, int r) {
    l = max(l, 1ll);
    if (r < l) {
      return 0ll;
    }
    int res = p[r][r] - p[l - 1][r] - p[r][l - 1] + p[l - 1][l - 1];
    return res;
  };
  vector<vector<int>> dp(n + 10, vector<int>(m + 10, 1e12));
  vector<vector<int>> bt(n + 10, vector<int>(m + 10));
  for (int i = 0; i <= m; ++i) {
    dp[i][i] = 0;
    bt[n + 1][i] = n;
  }
  for (int i = 0; i <= n; ++i) {
    bt[i][0] = 1;
  }
  for (int i = 0; i <= n; ++i) {}
  for (int j = 1; j <= m; ++j) {
    for (int i = n; i >= j + 1; --i) {
      for (int k = bt[i][j - 1]; k <= bt[i + 1][j]; ++k) {
        int cur = dp[k - 1][j - 1] + get_sum(k, i) / 2;
        if (cur < dp[i][j]) {
          dp[i][j] = cur;
          bt[i][j] = k;
        }
      }
    }
  }
  io.write(dp[n][m]);
}