分治优化DP

Link

\(\text{Para.1} \hspace{0.2cm}\)四边形不等式

对于形如 \(\text{dp}[i][j] = \min_{k<j}{\text{dp}[i-1][k] + \text{cost}[k+1][j]}\) 的形式，若 \(\text{cost}\) 满足 \(\text{cost}[a][c] + \text{cost}[b][d] \leq \text{cost}[a][d] + \text{cost}[b][c] (a\leq b\leq c \leq d)\) ，则 \(\text{dp}\) 满足上述不等式。

\(\text{Para.2}\hspace{0.2cm}\) 分治的引入

因为具有四边形不等式，所以就有决策单调性：\(\text{opt}[i][1] \leq \text{opt}[i][2] \leq ... \leq \text{opt}[i][j]\)。
那么如果我们每一次将中点的最优决策点计算出来，那么我们就可以将计算的规模减半。实现分治的功能。

\(\text{Para.3} \hspace{0.2cm}\) 基础代码

以 Ciel and Gondolas 为例：

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 4005;
const int M = 805;
int dp[M][N], n, k;
int sum[N][N], a[N][N];
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int cost(int i, int j) { return sum[j][j] - sum[i - 1][j] - sum[j][i - 1] + sum[i - 1][i - 1]; }
void DIV(int d, int l, int r, int optl, int optr) {
    if (l > r)
        return;
    int mid = (l + r) / 2;
    int cur = INT_MAX, opt;
    for (int k = optl; k <= optr; ++k) {
        int cst = dp[d - 1][k - 1] + cost(k, mid);
        if (cst < cur)
            cur = cst, opt = k;
    }
    dp[d][mid] = cur;
    DIV(d, l, mid - 1, optl, opt);
    DIV(d, mid + 1, r, opt, optr);
}
int main() {
	n = read(), k = read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
        	a[i][j] = read();
            sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= k; ++i) DIV(i, 1, n, 1, n);
    cout << dp[k][n] / 2 << '\n';
    return 0;
}

\(\text{Para.4} \hspace{0.2cm}\) 例题

1.Circular Barn

枚举第一个们开在哪，破环为链。

2.Guards

板子。

3.The Bakery

较难想，用莫队维护 \(\text{cost}\) 。

4.Lannister Army

板子。