Divide and Conquer DP and Knuth

Điểm tối ưu đơn điệu

Xét một tầng: $g[i] = \min_{j < i} f[j] + cost(j + 1, i)$, với $f$ là tầng trước. Gọi $opt(i)$ là $j$ nhỏ nhất đạt min. Nhiều chi phí thỏa $opt(1) \le opt(2) \le \dots \le opt(n)$: đoạn cuối kết thúc càng xa thì điểm bắt đầu của nó càng không lùi. Khi đó tính $g$ bằng chia để trị: tính $g[mid]$ cho $mid$ ở giữa bằng cách thử mọi $j$ trong khoảng ứng viên $[optL, optR]$; được $opt(mid)$, thì nửa trái chỉ cần thử $j \in [optL, opt(mid)]$, nửa phải $j \in [opt(mid), optR]$. Mỗi tầng đệ quy có tổng độ dài các khoảng ứng viên $O(n)$, có $\log n$ tầng, nên một lớp tốn $O(n \log n)$, $k$ lớp tốn $O(kn \log n)$.

Điều kiện đủ hay dùng là bất đẳng thức tứ giác: $cost(a, c) + cost(b, d) \le cost(a, d) + cost(b, c)$ với mọi $a \le b \le c \le d$. Bình phương tổng đoạn, số cặp bằng nhau trong đoạn, tổng khoảng cách tới trung vị đều thỏa. Trong lúc thi, cách kiểm nhanh nhất là chạy bản $O(kn^2)$ trên dữ liệu ngẫu nhiên nhỏ, in $opt$ và xem có giảm lần nào không.

Ví dụBình Phương Các Khối

Đề. Dãy $n \le 3000$ số dương, chia thành đúng $k$ đoạn, chi phí mỗi đoạn là bình phương tổng của nó. Tìm tổng nhỏ nhất.

Lời giải. $f_t[i]$ là chi phí nhỏ nhất chia $i$ phần tử đầu thành $t$ đoạn: $f_t[i] = \min_j f_{t-1}[j] + cost(j + 1, i)$ với $cost(l, r) = (P_r - P_{l-1})^2$, $P$ là tổng tiền tố. Điểm chia tốt nhất $opt(i)$ không giảm theo $i$, nên mỗi tầng tính được bằng chia để trị như trên trong $O(n \log n)$ thay vì $O(n^2)$.

Bước 1: chi phí một đoạn. Tổng tiền tố tính tại chỗ khi đọc.

ll cost(ll l, ll r) {
    return (pre[r] - pre[l - 1]) * (pre[r] - pre[l - 1]);
}

Bước 2: chia để trị một tầng. f là tầng $t - 1$, g là tầng $t$. solve(l, r, optl, optr) tính g[mid] bằng cách thử mọi $j$ trong khoảng ứng viên $[optl, \min(mid - 1, optr)]$ và nhớ $j$ tốt nhất bo; rồi nửa trái chỉ thử $j \le bo$, nửa phải chỉ thử $j \ge bo$. Bỏ qua f[j] == INF (tiền tố chưa chia được thành $t - 1$ đoạn) để khỏi cộng tràn.

void solve(ll l, ll r, ll optl, ll optr) {
    if (l > r) return;
    ll mid = (l + r) >> 1, best = INF, bo = optl;
    for (ll j = optl; j <= min(mid - 1, optr); j++) {
        if (f[j] == INF) continue;
        ll v = f[j] + cost(j + 1, mid);
        if (v < best) {
            best = v;
            bo = j;
        }
    }
    g[mid] = best;
    solve(l, mid - 1, optl, bo);
    solve(mid + 1, r, bo, optr);
}

Bước 3: $k$ tầng. Tầng 0 chỉ có f[0] = 0; mỗi tầng g[0] = INF vì không chia 0 phần tử thành $t \ge 1$ đoạn, xong thì chép g sang f.

for (ll t = 1; t <= k; t++) {
    g[0] = INF;
    solve(1, n, 0, n - 1);
    for (ll i = 0; i <= n; i++) f[i] = g[i];
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 3005, INF = 4e18;
ll n, k, pre[N], f[N], g[N];

ll cost(ll l, ll r) {
    return (pre[r] - pre[l - 1]) * (pre[r] - pre[l - 1]);
}

void solve(ll l, ll r, ll optl, ll optr) {
    if (l > r) return;
    ll mid = (l + r) >> 1, best = INF, bo = optl;
    for (ll j = optl; j <= min(mid - 1, optr); j++) {
        if (f[j] == INF) continue;
        ll v = f[j] + cost(j + 1, mid);
        if (v < best) {
            best = v;
            bo = j;
        }
    }
    g[mid] = best;
    solve(l, mid - 1, optl, bo);
    solve(mid + 1, r, bo, optr);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> pre[i];
        pre[i] += pre[i - 1];
        f[i] = INF;
    }
    for (ll t = 1; t <= k; t++) {
        g[0] = INF;
        solve(1, n, 0, n - 1);
        for (ll i = 0; i <= n; i++) f[i] = g[i];
    }
    cout << f[n] << '\n';
}

Input5 2
1 3 2 4 2

Output72

Mỗi tầng đệ quy của solve thử tổng cộng $O(n)$ ứng viên, có $\log n$ tầng: $O(kn \log n) \approx 10^8$ phép, so với $O(kn^2) = 2{,}7 \cdot 10^{10}$.

Chi phí từ tổng tiền tố hai chiều

Khi chi phí của đoạn $[l, r]$ là tổng một ma trận trên hình vuông $[l, r] \times [l, r]$, như tổng xung đột giữa mọi cặp người cùng toa, tổng tiền tố hai chiều (bài 02) cho nó trong $O(1)$: $sq(l, r) = S_{r,r} - S_{l-1,r} - S_{r,l-1} + S_{l-1,l-1}$, và chi phí là một nửa vì mỗi cặp được đếm hai lần. Chi phí này thỏa bất đẳng thức tứ giác khi các phần tử ma trận không âm. Với $n$ cỡ vài nghìn, chú ý bộ nhớ: bảng $4001 \times 4001$ số int khoảng 64 MB.

Ví dụCác Toa Yên Tĩnh

Đề. $N \le 4000$ hành khách xếp hàng, ma trận xung đột $u$ là chữ số 0 đến 9. Chia thành đúng $K \le 800$ toa (đoạn liên tiếp), chi phí mỗi toa là tổng $u_{ij}$ trên các cặp trong toa. Tìm tổng nhỏ nhất.

Lời giải. Cùng khuôn chia để trị như ví dụ trước; chỉ đổi hàm chi phí. Chi phí một toa $[l, r]$ là tổng $u_{ij}$ trên các cặp trong toa, lấy ra trong $O(1)$ từ tổng tiền tố hai chiều.

Bước 1: tổng tiền tố hai chiều khi đọc. Mỗi hàng ma trận là một xâu chữ số, cộng dồn ngay. Giá trị không quá $9 \cdot 4000^2 \approx 1{,}4 \cdot 10^8$ nên dùng int, để bảng $4005^2$ chỉ tốn khoảng 64 MB.

for (ll i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (ll j = 1; j <= n; j++) S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (s[j - 1] - '0');
}

Bước 2: chi phí một toa. Lấy tổng hình vuông $[l, r]^2$ rồi chia 2 vì mỗi cặp nằm hai lần trong ma trận đối xứng (đường chéo bằng 0).

int cost(ll l, ll r) {
    return (S[r][r] - S[l - 1][r] - S[r][l - 1] + S[l - 1][l - 1]) / 2;
}

Bước 3: $K$ tầng chia để trị. Hàm solve giống hệt ví dụ trước, đổi sang int.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 4005;
const int INF = 2e9;
ll n, k;
int S[N][N], f[N], g[N];

int cost(ll l, ll r) {
    return (S[r][r] - S[l - 1][r] - S[r][l - 1] + S[l - 1][l - 1]) / 2;
}

void solve(ll l, ll r, ll optl, ll optr) {
    if (l > r) return;
    ll mid = (l + r) >> 1, bo = optl;
    int best = INF;
    for (ll j = optl; j <= min(mid - 1, optr); j++) {
        if (f[j] == INF) continue;
        int v = f[j] + cost(j + 1, mid);
        if (v < best) {
            best = v;
            bo = j;
        }
    }
    g[mid] = best;
    solve(l, mid - 1, optl, bo);
    solve(mid + 1, r, bo, optr);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (ll j = 1; j <= n; j++) S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (s[j - 1] - '0');
    }
    for (ll i = 1; i <= n; i++) f[i] = INF;
    for (ll t = 1; t <= k; t++) {
        g[0] = INF;
        solve(1, n, 0, n - 1);
        for (ll i = 0; i <= n; i++) f[i] = g[i];
    }
    cout << f[n] << '\n';
}

Input5 2
02879
20168
81027
76201
98710

Output12

Khoảng $800 \cdot 4000 \cdot 12 \approx 4 \cdot 10^7$ lần tính chi phí.

Chi phí tính bằng hai con trỏ

Có chi phí không tách được thành hiệu các tổng tiền tố, như số cặp phần tử bằng nhau trong đoạn. Nhưng trong chia để trị, các đoạn được hỏi liên tiếp nhau thay đổi rất ít: với một $mid$, $j$ chạy liên tục trong khoảng ứng viên; sang lời gọi con, $mid$ và khoảng ứng viên chỉ dời một nửa. Giữ một cửa sổ $[L, R]$ cùng bảng đếm như thuật toán Mo (bài 25), mỗi lần hỏi thì dời hai biên tới đoạn cần. Tổng số bước dời của một lớp là $O(n \log n)$, nên cả bài $O(kn \log n)$ với hằng số nhỏ.

Ví dụCặp Trùng Trong Đoạn

Đề. Dãy $N \le 10^5$ số, chia thành đúng $K \le 20$ đoạn. Chi phí một đoạn là số cặp chỉ số trong nó có giá trị bằng nhau. Tìm tổng nhỏ nhất.

Lời giải. Chi phí số cặp trùng thỏa bất đẳng thức tứ giác, nên điểm chia tốt nhất đơn điệu và chia để trị dùng được. Khó khăn là chi phí không có công thức $O(1)$. Nhưng trong solve, các đoạn được hỏi thay đổi từng chút một, nên tính chi phí bằng một cửa sổ kiểu Mo (bài 25): giữ cửa sổ hiện tại và dời hai biên tới đoạn cần hỏi.

Bước 1: cửa sổ đếm cặp trùng. cl, cr, cur là cửa sổ hiện tại và số cặp trùng trong đó; cnt đếm số lần mỗi giá trị. Phần tử mới tạo thêm cnt[a[i]] cặp với các bản đã có, rồi tăng đếm; bỏ thì làm ngược lại.

void add(ll i) {
    cur += cnt[a[i]]++;
}

void del(ll i) {
    cur -= --cnt[a[i]];
}

Bước 2: dời cửa sổ tới $[l, r]$. Mở rộng hai biên trước, rồi mới thu hẹp, để cửa sổ không bao giờ “âm”.

ll cost(ll l, ll r) {
    while (cr < r) add(++cr);
    while (cl > l) add(--cl);
    while (cr > r) del(cr--);
    while (cl < l) del(cl++);
    return cur;
}

Bước 3: chia để trị giống hệt các ví dụ trước. Trong solve, các đoạn $[j + 1, mid]$ được hỏi theo $j$ tăng dần, mỗi lần biên trái dời một bước; giữa các lời gọi, $mid$ và khoảng ứng viên đổi theo cấu trúc chia đôi. Đề bảo đảm giá trị không quá $N$ nên cnt dùng mảng trực tiếp.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, INF = 4e18;
ll n, k, a[N], cnt[N], f[N], g[N], cl = 1, cr = 0, cur = 0;

void add(ll i) {
    cur += cnt[a[i]]++;
}

void del(ll i) {
    cur -= --cnt[a[i]];
}

ll cost(ll l, ll r) {
    while (cr < r) add(++cr);
    while (cl > l) add(--cl);
    while (cr > r) del(cr--);
    while (cl < l) del(cl++);
    return cur;
}

void solve(ll l, ll r, ll optl, ll optr) {
    if (l > r) return;
    ll mid = (l + r) >> 1, best = INF, bo = optl;
    for (ll j = optl; j <= min(mid - 1, optr); j++) {
        if (f[j] == INF) continue;
        ll v = f[j] + cost(j + 1, mid);
        if (v < best) {
            best = v;
            bo = j;
        }
    }
    g[mid] = best;
    solve(l, mid - 1, optl, bo);
    solve(mid + 1, r, bo, optr);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = INF;
    }
    for (ll t = 1; t <= k; t++) {
        g[0] = INF;
        solve(1, n, 0, n - 1);
        for (ll i = 0; i <= n; i++) f[i] = g[i];
    }
    cout << f[n] << '\n';
}

Input7 3
1 1 3 3 3 2 1

Output1

Tổng số bước dời cửa sổ của một tầng là $O(n \log n)$: cả bài $O(Kn \log n)$.

Knuth cho quy hoạch động trên đoạn

Ghép các khối kề nhau, cắt thanh theo nhiều điểm, dựng cây tìm kiếm tối ưu: $dp[l][r] = \min_{l \le m < r} dp[l][m] + dp[m+1][r] + w(l, r)$. Nếu $w$ thỏa bất đẳng thức tứ giác và đơn điệu theo bao hàm ($w(b, c) \le w(a, d)$ khi $[b, c] \subseteq [a, d]$), thì điểm chia tốt nhất thỏa

Tính $dp$ theo độ dài đoạn tăng dần, và với đoạn $[l, r]$ chỉ thử $m$ trong khoảng trên. Tổng số lần thử trên mọi đoạn cùng độ dài là một tổng lồng: $\sum_l (opt[l+1][r] - opt[l][r-1] + 1) = O(n)$, nên cả bài $O(n^2)$ thay cho $O(n^3)$.

Ví dụGhép Theo Thứ Tự

Đề. $T \le 10$ bộ, mỗi bộ $K \le 5000$ khối xếp hàng. Ghép hai khối kề tốn tổng kích thước của chúng. Tìm tổng chi phí nhỏ nhất để ghép tất cả thành một.

Lời giải. Quy hoạch động khoảng: $dp[l][r] = \min_m (dp[l][m] + dp[m+1][r]) + w(l, r)$, với $w(l, r)$ là tổng kích thước đoạn. $w$ thỏa cả hai điều kiện của Knuth, nên điểm chia tốt nhất kẹp giữa $opt[l][r-1]$ và $opt[l+1][r]$. Bảng $5000 \times 5000$ khá nặng: chi phí tối ưu không quá tổng kích thước nhân $\lceil \log_2 K \rceil$ (gộp kiểu cây cân bằng), khoảng $6{,}5 \cdot 10^8$, nên dp dùng int; opt dùng short vì chỉ số không quá 5000. Tổng hai bảng khoảng 150 MB.

Bước 1: đoạn độ dài 1. dp = 0, opt = i; tổng tiền tố tính ngay khi đọc.

for (ll i = 1; i <= n; i++) {
    cin >> pre[i];
    pre[i] += pre[i - 1];
    dp[i][i] = 0;
    opt[i][i] = i;
}

Bước 2: đoạn dài dần, chỉ thử trong khoảng kẹp. Đoạn $[l, r]$ chỉ thử $m$ từ opt[l][r - 1] tới opt[l + 1][r] (kẹp không quá $r - 1$); hai giá trị này đã có vì đoạn ngắn hơn được tính trước. $w(l, r)$ cộng sau khi chọn $m$, vì không phụ thuộc $m$.

for (ll len = 2; len <= n; len++)
    for (ll l = 1; l + len - 1 <= n; l++) {
        ll r = l + len - 1, lo = opt[l][r - 1], hi = min((ll)opt[l + 1][r], r - 1);
        int best = INF;
        ll bm = lo;
        for (ll m = lo; m <= hi; m++) {
            int v = dp[l][m] + dp[m + 1][r];
            if (v < best) {
                best = v;
                bm = m;
            }
        }
        dp[l][r] = best + (pre[r] - pre[l - 1]);
        opt[l][r] = bm;
    }

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 5005;
const int INF = 2e9;
int dp[N][N];
short opt[N][N];
ll pre[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        for (ll i = 1; i <= n; i++) {
            cin >> pre[i];
            pre[i] += pre[i - 1];
            dp[i][i] = 0;
            opt[i][i] = i;
        }
        for (ll len = 2; len <= n; len++)
            for (ll l = 1; l + len - 1 <= n; l++) {
                ll r = l + len - 1, lo = opt[l][r - 1], hi = min((ll)opt[l + 1][r], r - 1);
                int best = INF;
                ll bm = lo;
                for (ll m = lo; m <= hi; m++) {
                    int v = dp[l][m] + dp[m + 1][r];
                    if (v < best) {
                        best = v;
                        bm = m;
                    }
                }
                dp[l][r] = best + (pre[r] - pre[l - 1]);
                opt[l][r] = bm;
            }
        cout << dp[1][n] << '\n';
    }
}

Input2
3
5 1 4
4
8 2 2 8

Output15
36

Với một độ dài cố định, khoảng thử của các đoạn liền nhau nối đuôi nhau, tổng độ dài không quá $n$ cộng số đoạn: cả bài $O(n^2)$ thay vì $O(n^3)$.