Advanced DP

Mảng đuôi

Công thức quen của dãy con tăng dài nhất (bài 12) là $\mathrm{dp}[i] = 1 + \max \mathrm{dp}[j]$ trên các $j < i$ có $a_j < a_i$, tốn $O(n^2)$.

Đổi góc nhìn: thay vì nhớ độ dài tốt nhất kết thúc tại từng vị trí, nhớ với mỗi độ dài $k$ phần tử cuối nhỏ nhất của một dãy con tăng dài $k$, gọi là tail[k - 1] (đánh số từ 0). Đuôi càng nhỏ thì càng dễ nối thêm, nên dãy cùng độ dài mà đuôi lớn hơn bị trội, không cần nhớ.

Mảng tail tăng nghiêm ngặt: một dãy dài $k + 1$ có đuôi $t$ chứa một dãy dài $k$ có đuôi nhỏ hơn $t$. Đọc $a_i$, tìm vị trí đầu tiên trong tail có giá trị $\ge a_i$ bằng tìm kiếm nhị phân. Không có thì $a_i$ nối vào dãy dài nhất, tail dài thêm 1; có thì $a_i$ là đuôi nhỏ hơn cho độ dài đó, ghi đè. Độ dài cuối của tail là đáp án.

tail không phải một dãy con thật của đầu vào: các giá trị trong nó có thể đến từ những dãy khác nhau. Muốn in một dãy con tối ưu, lưu thêm với mỗi $i$ vị trí của phần tử đứng trước nó lúc chèn, rồi lần ngược. Dãy con không giảm thì dùng upper_bound thay cho lower_bound.

Ba cách làm trên 50 nghìn số ngẫu nhiên:

Quy hoạch động $O(n^2)$ chậm hơn mảng đuôi hàng nghìn lần, và Fenwick chậm hơn mảng đuôi cỡ 6 lần. Fenwick đáng dùng khi bài có trọng số hay phải đếm, còn dãy con tăng dài nhất thuần túy thì mảng đuôi là gọn nhất.

Ví dụNhững Mốc Tăng Dần

Đề. Dãy $n \le 2 \cdot 10^5$ số. Tìm độ dài dãy con tăng nghiêm ngặt dài nhất.

Lời giải. Mảng đuôi với lower_bound, $O(n \log n)$. Công thức $O(n^2)$ cần $4 \cdot 10^{10}$ phép ở giới hạn này. Với ví dụ, tail lần lượt là 5, 1, 1 4, 1 2, 1 2 3, 1 2 3 9, 1 2 3 6, 1 2 3 6 7.

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

ll n;
vector<ll> tail;

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        ll p = lower_bound(tail.begin(), tail.end(), x) - tail.begin();
        if (p == (ll)tail.size()) tail.push_back(x);
        else tail[p] = x;
    }
    cout << tail.size() << '\n';
}

ChạyInput8
5 1 4 2 3 9 6 7

Output5

Fenwick theo giá trị

Chuyển tiếp “lấy max (hay tổng) $\mathrm{dp}[j]$ trên mọi $j < i$ có $a_j < a_i$” có hai điều kiện. Điều kiện $j < i$ tự thỏa nếu xử lý $i$ từ trái sang và chỉ ghi $\mathrm{dp}[j]$ vào cấu trúc sau khi tính xong. Điều kiện $a_j < a_i$ thành một tiền tố trên miền giá trị: lập Fenwick (bài 16) chỉ số theo giá trị, ghi $\mathrm{dp}[j]$ vào ô $a_j$, hỏi tiền tố $[1, a_i - 1]$. Giá trị lớn thì nén về $1..n$ trước.

Fenwick hỏi tiền tố được cả max (khi giá trị trong ô chỉ tăng) lẫn tổng. Cùng khuôn đó giải dãy con tăng có trọng số lớn nhất, đếm số dãy con tăng, đếm dãy con tăng có đúng $k$ phần tử (mỗi độ dài một Fenwick). Điều kiện $|a_j - a_i| \ge d$ là hai tiền tố, hoặc một tiền tố và một hậu tố, trên miền giá trị; khi đó dùng cây phân đoạn hỏi đoạn.

Ví dụVườn Hoa Có Thứ Tự

Đề. $n \le 2 \cdot 10^5$ bông hoa, bông $i$ cao $h_i$ (một hoán vị của $1..n$) và có giá trị $b_i$. Giữ lại các bông có chiều cao tăng dần từ trái sang, tổng giá trị lớn nhất.

Lời giải. $\mathrm{dp}[i] = b_i + \max \mathrm{dp}[j]$ trên $j < i$, $h_j < h_i$. Fenwick max theo chiều cao: hỏi tiền tố $h_i - 1$, rồi ghi $\mathrm{dp}[i]$ vào ô $h_i$. Đáp án là max mọi $\mathrm{dp}$, tới $2 \cdot 10^{14}$, cần ll. Với ví dụ, bông thứ 6 cao 3 lấy max của các bông cao 1, 2 là 30 và cộng 30.

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

const ll N = 2e5 + 5;
ll n, h[N], b[N], bit[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] = max(bit[pos], val);
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res = max(res, bit[pos]);
    return res;
}

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

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> h[i];
    for (ll i = 1; i <= n; i++) cin >> b[i];
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ll cur = b[i] + get(h[i] - 1);
        update(h[i], cur);
        ans = max(ans, cur);
    }
    cout << ans << '\n';
}

ChạyInput6
4 1 5 2 6 3
8 10 4 20 7 30

Output60

Tổng tiền tố

Khi các $j$ hợp lệ của $\mathrm{dp}[i]$ tạo thành một đoạn liền $[L_i, R_i]$ và $\mathrm{dp}$ cần tổng (hay chỉ cần biết có tồn tại), tổng tiền tố của chính mảng $\mathrm{dp}$ trả lời trong $O(1)$: tính $\mathrm{dp}[i]$ xong thì cập nhật $S_i = S_{i-1} + \mathrm{dp}[i]$. Hai đầu $L_i, R_i$ thường đơn điệu theo $i$, tìm bằng hai con trỏ (bài 06) hoặc tìm kiếm nhị phân. Cùng ý tưởng làm đếm số cách đi bậc thang với bước tối đa $k$ thành $O(n)$, và đếm dãy nằm giữa hai biên thành tổng tiền tố theo giá trị.

Ví dụChia Nhóm Theo Độ Chênh

Đề. $n \le 5 \cdot 10^5$ thẻ có giá trị. Hỏi có chia được toàn bộ thẻ thành các nhóm, mỗi nhóm ít nhất $k$ thẻ và chênh lệch lớn nhất trong nhóm không quá $d$, hay không.

Lời giải. Sắp tăng dần; có cách chia thì có cách chia mà mỗi nhóm là một đoạn liền của dãy đã sắp (đổi chỗ hai thẻ lệch giữa hai nhóm không làm hỏng điều kiện). $\mathrm{ok}[i]$: $i$ thẻ đầu chia được. Nhóm cuối là $[j + 1, i]$, cần $j \le i - k$ và $a_i - a_{j+1} \le d$, tức $j \ge lo_i - 1$ với $lo_i$ là thẻ đầu tiên có $a \ge a_i - d$. Vậy $\mathrm{ok}[i]$ đúng khi có $\mathrm{ok}[j]$ đúng với $j$ trong đoạn $[lo_i - 1, i - k]$; $lo_i$ tăng theo $i$ nên dùng con trỏ, còn đoạn thì hỏi bằng tổng tiền tố của $\mathrm{ok}$. Với ví dụ, sau khi sắp là $1, 2, 3, 10, 11, 12, 12$, chia sau thẻ thứ 3.

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

const ll N = 5e5 + 5;
ll n, k, d, a[N], ok[N], pre[N];

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

    cin >> n >> k >> d;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    ok[0] = pre[0] = 1;
    for (ll i = 1, lo = 1; i <= n; i++) {
        while (a[i] - a[lo] > d) lo++;
        ll L = lo - 1, R = i - k;
        if (R >= L) ok[i] = pre[R] - (L ? pre[L - 1] : 0) > 0;
        pre[i] = pre[i - 1] + ok[i];
    }
    cout << (ok[n] ? "YES" : "NO") << '\n';
}

ChạyInput7 3 2
12 1 11 3 10 2 12

OutputYES

Cửa sổ trượt

Chuyển tiếp lấy max trên một cửa sổ $[i - k, i - 1]$ trượt theo $i$ không dùng được tổng tiền tố. Hàng đợi đơn điệu (bài 06) giữ các chỉ số trong cửa sổ theo thứ tự, giá trị $\mathrm{dp}$ giảm dần: thêm chỉ số mới ở cuối thì bỏ hết các chỉ số cuối có giá trị không lớn hơn, vì chúng vừa cũ hơn vừa kém hơn; chỉ số đầu hàng rời cửa sổ thì bỏ ở đầu. Đầu hàng luôn là max của cửa sổ. Mỗi chỉ số vào và ra một lần, nên cả lượt $O(n)$ thay cho $O(nk)$.

Cách khác là giữ cửa sổ trong multiset, mất $O(\log k)$ mỗi bước:

Hàng đợi đơn điệu nhanh hơn multiset khoảng 20 lần. Cửa sổ trượt cần max hay min thì dùng hàng đợi, không dùng set.

Ví dụChọn Ảnh Phủ Mọi Cửa Sổ

Đề. $n \le 5000$ ảnh có độ đẹp. Chọn đúng $x$ ảnh sao cho mọi đoạn $k$ ảnh liên tiếp chứa ít nhất một ảnh được chọn, tổng độ đẹp lớn nhất; không chọn được thì in $-1$.

Lời giải. Điều kiện tương đương: ảnh chọn đầu tiên ở vị trí $\le k$, ảnh cuối ở vị trí $> n - k$, và hai ảnh liên tiếp cách nhau không quá $k$. $\mathrm{dp}[j][i]$ là tổng lớn nhất khi chọn $j$ ảnh, ảnh cuối ở $i$: $\mathrm{dp}[j][i] = a_i + \max \mathrm{dp}[j-1][p]$ trên $p \in [i - k, i - 1]$, với $\mathrm{dp}[0][0] = 0$ và mọi trạng thái khác của tầng 0 là $-\infty$ để ép ảnh đầu ở vị trí $\le k$. Mỗi tầng một lượt hàng đợi đơn điệu, tổng $O(nx) = 2{,}5 \cdot 10^7$; chỉ giữ hai tầng để bộ nhớ $O(n)$.

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

const ll N = 5005, NEG = -1e18;
ll n, k, x, a[N], f[N], g[N], dq[N];

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

    cin >> n >> k >> x;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) f[i] = NEG;
    for (ll j = 1; j <= x; j++) {
        ll h = 0, t = 0;
        g[0] = NEG;
        for (ll i = 1; i <= n; i++) {
            while (t > h && f[dq[t - 1]] <= f[i - 1]) t--;
            dq[t++] = i - 1;
            while (dq[h] < i - k) h++;
            g[i] = f[dq[h]] == NEG ? NEG : f[dq[h]] + a[i];
        }
        for (ll i = 0; i <= n; i++) f[i] = g[i];
    }
    ll ans = NEG;
    for (ll i = n - k + 1; i <= n; i++) ans = max(ans, f[i]);
    cout << (ans == NEG ? -1 : ans) << '\n';
}

ChạyInput6 3 2
4 9 1 8 2 7

Output17

Cây phân đoạn

Có bài mà mỗi bước không chỉ tính một $\mathrm{dp}[i]$ mới, mà còn làm thay đổi cả một đoạn các giá trị cũ: thêm một khoảng có trọng số thì mọi lựa chọn “điểm chọn cuối nằm trong khoảng” cùng được cộng trọng số. Đặt cả mảng $\mathrm{dp}[0..n]$ lên cây phân đoạn có cộng đoạn lười và hỏi max đoạn (bài 17): mỗi bước là một câu hỏi max, một lần gán điểm và vài lần cộng đoạn, $O(\log n)$ mỗi thao tác.

Khuôn này còn giải chia dãy thành $k$ đoạn với giá trị mỗi đoạn là số phần tử khác nhau: khi thêm $a_i$, mọi đoạn bắt đầu sau lần xuất hiện trước của $a_i$ được cộng 1.

Ví dụChọn Điểm Để Kích Hoạt Các Khoảng

Đề. $N \le 2 \cdot 10^5$ vị trí, $M \le 2 \cdot 10^5$ khoảng $[l, r]$ có trọng số $a$ (có thể âm). Chọn một tập vị trí; mỗi khoảng chứa ít nhất một vị trí được chọn cho điểm $a$. Tìm tổng điểm lớn nhất.

Lời giải. Mỗi khoảng chỉ cần biết vị trí được chọn cuối cùng không quá $r$ của nó có $\ge l$ hay không. Gọi $\mathrm{val}[j]$ là điểm tốt nhất khi vị trí chọn cuối là $j$ ($j = 0$: chưa chọn gì), chỉ tính các khoảng đã kết thúc. Quét $i$ từ 1 tới $N$:

• Chọn $i$ thì vị trí chọn trước đó có thể là bất kỳ $j < i$: $\mathrm{val}[i] = \max(\mathrm{val}[0..i-1])$.
• Mỗi khoảng $[l, i]$ kết thúc ở $i$ được kích hoạt đúng khi vị trí chọn cuối nằm trong $[l, i]$: cộng $a$ vào $\mathrm{val}[l..i]$.

Đáp án là max toàn mảng sau khi quét hết. Hai thao tác là “gán một ô bằng max một đoạn” và “cộng một đoạn”, nên dùng cây phân đoạn max có thẻ cộng.

Bước 1: cây max với thẻ cộng. Như cây lười ở bài 17: apply cộng vào giá trị và thẻ của nút; down đẩy thẻ cho hai con. Ở đây nút lưu max nên cộng $v$ vào cả đoạn làm max tăng đúng $v$, không cần biết độ dài đoạn.

void apply(ll id, ll val) {
    st[id] += val;
    lz[id] += val;
}

void down(ll id) {
    if (!lz[id]) return;
    apply(id * 2, lz[id]);
    apply(id * 2 + 1, lz[id]);
    lz[id] = 0;
}

Bước 2: gom khoảng theo đầu phải. at[r] là danh sách các khoảng kết thúc ở $r$, mỗi khoảng lưu $(l, a)$.

for (ll i = 1; i <= m; i++) {
    ll l, r, a;
    cin >> l >> r >> a;
    at[r].push_back({l, a});
}

Bước 3: quét. Cây đánh số $0..N$. Gán $\mathrm{val}[i]$ bằng cách cộng max của $[0, i - 1]$ vào ô $i$: ô $i$ chưa được chạm tới trước đó nên đang bằng 0. Rồi cộng trọng số của từng khoảng kết thúc ở $i$.

for (ll i = 1; i <= n; i++) {
    update(1, 0, n, i, i, get(1, 0, n, 0, i - 1));
    for (pair<ll, ll> p : at[i]) update(1, 0, n, p.first, i, p.second);
}
cout << get(1, 0, n, 0, n) << '\n';

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

const ll N = 2e5 + 5, NEG = -1e18;
ll n, m, st[4 * N], lz[4 * N];
vector<pair<ll, ll>> at[N];

void apply(ll id, ll val) {
    st[id] += val;
    lz[id] += val;
}

void down(ll id) {
    if (!lz[id]) return;
    apply(id * 2, lz[id]);
    apply(id * 2 + 1, lz[id]);
    lz[id] = 0;
}

void update(ll id, ll l, ll r, ll u, ll v, ll val) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        apply(id, val);
        return;
    }
    down(id);
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

ll get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return NEG;
    if (u <= l && r <= v) return st[id];
    down(id);
    ll mid = (l + r) >> 1;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

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

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll l, r, a;
        cin >> l >> r >> a;
        at[r].push_back({l, a});
    }
    for (ll i = 1; i <= n; i++) {
        update(1, 0, n, i, i, get(1, 0, n, 0, i - 1));
        for (pair<ll, ll> p : at[i]) update(1, 0, n, p.first, i, p.second);
    }
    cout << get(1, 0, n, 0, n) << '\n';
}

ChạyInput4 4
1 2 5
2 4 7
1 4 -4
3 3 -10

Output8

Độ phức tạp: mỗi vị trí và mỗi khoảng tốn $O(\log N)$: tổng $O((N + M) \log N)$.