Aliens Trick

Phạt mỗi lần chọn

Cần $\max$ trên mọi phương án có không quá $K$ đoạn. Gọi $f(k)$ là giá trị tốt nhất khi dùng đúng $k$ đoạn. Với khoản phạt $\lambda \ge 0$ trừ vào mỗi đoạn, giải bài không giới hạn số đoạn:

Đây là DP thường, không có chiều $k$, chỉ ghi kèm số đoạn của phương án tối ưu. Phạt càng lớn thì số đoạn tối ưu càng nhỏ. Nếu $f$ lõm (lợi ích của đoạn thêm vào giảm dần), mọi $k$ đều là tối ưu ở một $\lambda$ nào đó: các đường $f(k) - \lambda k$ theo $\lambda$ tạo thành bao lồi mà không đường nào bị che khuất. Tìm $\lambda$ để số đoạn tối ưu bằng $K$ thì $f(K) = g(\lambda) + \lambda K$.

Hình dưới là bài mẫu: chọn $k$ phần tử không kề nhau, tổng lớn nhất. Mỗi đường là $f(k) - \lambda k$ theo $\lambda$. Kéo $\lambda$: đường cao nhất (cam) cho $k$ tối ưu và các ô được chọn.

Khi nhiều $k$ cùng tối ưu. Với $f$ nguyên và $\lambda$ nguyên, ở một số $\lambda$ cả đoạn $k \in [c_{\min}, c_{\max}]$ cùng tối ưu, và có thể không $\lambda$ nào cho đúng $K$ là duy nhất. Cố định cách phá hòa: luôn chọn số đoạn lớn nhất khi bằng giá trị, rồi tìm $\lambda$ lớn nhất còn có $c_{\max}(\lambda) \ge K$. Ở $\lambda + 1$ số đoạn tụt dưới $K$, nên $c_{\min}(\lambda) < K \le c_{\max}(\lambda)$: $K$ nằm trong đoạn tối ưu và $g(\lambda) + \lambda K$ vẫn đúng bằng $f(K)$. Ghép sai chiều (phá hòa chọn nhiều mà lại tìm $\lambda$ nhỏ nhất có $c_{\max} \le K$) sẽ lệch đúng một bậc ở các ca hòa.

Ví dụNhững Đoạn Hài Lòng

Đề. Dãy $N \le 3 \cdot 10^5$ số, $|A_i| \le 10^9$. Chọn không quá $K$ đoạn rời nhau, tổng phần tử được chọn lớn nhất.

Lời giải. Gọi $f(j)$ là tổng lớn nhất khi dùng đúng $j$ đoạn; $f$ lõm theo $j$. Thay ràng buộc số đoạn bằng mức phạt $\lambda$ mỗi lần mở đoạn mới, quy hoạch động không còn chiều $j$. Chặt nhị phân $\lambda \in [0, 3 \cdot 10^{14}]$ để số đoạn tối ưu chạm $K$.

Bước 1: quy hoạch động có phạt. Mỗi trạng thái là cặp (giá trị, số đoạn). in là đang ở trong một đoạn, out là đang ở ngoài. Vào đoạn từ ngoài thì trừ lam và tăng số đoạn; ở trong thì cộng tiếp $a_i$. LLONG_MIN / 4 làm trạng thái “không thể” mà cộng thêm vẫn không tràn.

pair<ll, ll> out = {0, 0}, in = {LLONG_MIN / 4, 0};
for (int i = 1; i <= n; i++) {
    pair<ll, ll> nin = max(make_pair(in.first + a[i], in.second), make_pair(out.first + a[i] - lam, out.second + 1));
    pair<ll, ll> nout = max(out, in);
    in = nin, out = nout;
}

So cặp bằng max của pair: giá trị bằng nhau thì lấy cặp có số đoạn lớn hơn. Quy ước phá hòa này phải giống nhau ở mọi chỗ, để số đoạn trả về là số lớn nhất trong các phương án tối ưu với mức phạt đó.

Bước 2: chặt mức phạt. Số đoạn chỉ giảm khi lam tăng. Tìm res lớn nhất mà số đoạn vẫn ít nhất $K$; tại đó đường thẳng độ dốc res chạm $f$ ở $K$, nên $f(K) = g(res) + res \cdot K$.

while (l <= h) {
    ll mid = (l + h) / 2;
    if (solve(mid).second >= k) res = mid, l = mid + 1;
    else h = mid - 1;
}
cout << solve(res).first + res * k << '\n';

Nếu ngay lam = 0 số đoạn đã dưới $K$ thì res = 0, và công thức cho đúng cực đại không giới hạn, tức đáp án của “không quá $K$”.

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

const int N = 3e5 + 5;
int n, k;
ll a[N];

pair<ll, ll> solve(ll lam) {
    pair<ll, ll> out = {0, 0}, in = {LLONG_MIN / 4, 0};
    for (int i = 1; i <= n; i++) {
        pair<ll, ll> nin = max(make_pair(in.first + a[i], in.second), make_pair(out.first + a[i] - lam, out.second + 1));
        pair<ll, ll> nout = max(out, in);
        in = nin, out = nout;
    }
    return max(out, in);
}

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll l = 0, h = 3e14, res = 0;
    while (l <= h) {
        ll mid = (l + h) / 2;
        if (solve(mid).second >= k) res = mid, l = mid + 1;
        else h = mid - 1;
    }
    cout << solve(res).first + res * k << '\n';
}

ChạyInput7 2
4 -6 5 3 -10 7 2

Output17

$O(N \log 3 \cdot 10^{14}) \approx 49N$. So với DP có chiều $K$ thì chênh lệch rất lớn:

Alien trick nhanh hơn DP có chiều $K$ khoảng 25 lần với $K = 1000$, và khoảng cách tăng theo $K$. Gộp cặp (giá trị, số đoạn) vào một số nguyên (giá trị nhân $2^{18}$ cộng số đoạn) nhanh thêm khoảng 1,5 lần nữa nhưng chỉ dùng được khi giá trị đủ nhỏ để không tràn.

Chọn không kề nhau

Bài cực tiểu thì làm đối xứng: thưởng $\lambda$ cho mỗi lần chọn (trừ vào chi phí), thưởng càng lớn càng chọn nhiều; $f(k)$ phải lồi. Tìm $\lambda$ nhỏ nhất có số lần chọn (phá hòa bằng chọn nhiều nhất) ít nhất $K$, đáp án $g(\lambda) + \lambda K$.

Bài chọn $K$ khoảng hở không kề nhau có $f(k)$ lồi: tương đương một luồng chi phí nhỏ nhất, mỗi đơn vị luồng thêm không rẻ hơn đơn vị trước. Kiểm tính lồi theo cách này, hoặc thử bằng brute force: in $f(k)$ cho $k$ nhỏ và xem hiệu kề có tăng dần không.

Ví dụCa Gác Tách Biệt

Đề. $N \le 5 \cdot 10^5$ thời điểm phân biệt, chọn $K \le 5000$ cuộc gặp (mỗi cuộc gặp dùng hai thời điểm làm đầu mút) không chồng nhau, không chung đầu mút, tổng độ dài nhỏ nhất.

Lời giải. Sắp các thời điểm; g[i] là khoảng hở thứ $i$ giữa hai thời điểm liên tiếp. Mỗi cuộc gặp tối ưu là một khoảng hở, và hai cuộc gặp không chung đầu mút nghĩa là hai khoảng được chọn không kề nhau. Bài cực tiểu nên dùng thưởng $\lambda$ cho mỗi lần chọn: thưởng càng lớn càng chọn nhiều. Chặt nhị phân $\lambda \in [0, 10^9]$.

Bước 1: quy hoạch động có thưởng. take là khoảng hở cuối được chọn, skip là không; chọn khoảng $i$ chỉ được từ skip, cộng g[i] - lam. Số lần chọn lưu dưới dạng số âm, để min trên cặp tự phá hòa theo hướng chọn nhiều hơn; hàm trả về đổi lại dấu dương.

pair<ll, ll> take = {LLONG_MAX / 4, 0}, skip = {0, 0};
for (int i = 1; i < n; i++) {
    pair<ll, ll> nt = {skip.first + g[i] - lam, skip.second - 1};
    pair<ll, ll> ns = min(take, skip);
    take = nt, skip = ns;
}
pair<ll, ll> r = min(take, skip);
return {r.first, -r.second};

Bước 2: chặt thưởng. Tìm res nhỏ nhất mà số lần chọn ít nhất $K$, rồi cộng lại res * k.

if (solve(mid).second >= k) res = mid, h = mid - 1;
else l = mid + 1;

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

const int N = 5e5 + 5;
int k, n;
ll t[N], g[N];

pair<ll, ll> solve(ll lam) {
    pair<ll, ll> take = {LLONG_MAX / 4, 0}, skip = {0, 0};
    for (int i = 1; i < n; i++) {
        pair<ll, ll> nt = {skip.first + g[i] - lam, skip.second - 1};
        pair<ll, ll> ns = min(take, skip);
        take = nt, skip = ns;
    }
    pair<ll, ll> r = min(take, skip);
    return {r.first, -r.second};
}

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

    cin >> k >> n;
    for (int i = 0; i < n; i++) cin >> t[i];
    sort(t, t + n);
    for (int i = 1; i < n; i++) g[i] = t[i] - t[i - 1];
    ll l = 0, h = 1e9, res = h;
    while (l <= h) {
        ll mid = (l + h) / 2;
        if (solve(mid).second >= k) res = mid, h = mid - 1;
        else l = mid + 1;
    }
    cout << solve(res).first + res * k << '\n';
}

ChạyInput2 6
10 1 4 20 21 7

Output4

Độ phức tạp: $O(N \log N + N \log 10^9)$.

Đúng K và đối xứng

Đề đòi đúng $K$ vẫn làm y hệt. Hàm $f(k)$ có thể chỉ lõm trên một nửa miền: tô $R$ bóng đỏ trong $N$ bóng để tổng thưởng các cặp kề khác màu lớn nhất có $f(R) = f(N - R)$ (đổi màu toàn bộ), và $f$ lõm trên $[0, N/2]$. Thay $R$ bằng $\min(R, N - R)$ rồi làm như thường.

Khoảng tìm $\lambda$: từ 0 tới lợi ích lớn nhất mà một lần chọn thêm có thể mang lại (ở đây $2 \max A_i$), cộng dư một ít.

Ví dụDãy Đèn Hai Màu

Đề. $N \le 2 \cdot 10^5$ bóng, $A_i \le 10^9$ là thưởng nếu bóng $i$ và $i + 1$ khác màu. Tô đúng $R$ bóng đỏ, tổng thưởng lớn nhất.

Lời giải. Đổi màu toàn bộ không đổi thưởng, nên chỉ cần xét $r = \min(R, N - R)$, phía mà $f$ lõm. Quy hoạch động theo màu bóng trước, phạt $\lambda$ mỗi bóng đỏ, phá hòa bằng max trên cặp để chọn nhiều đỏ hơn, như ví dụ đầu.

Bước 1: hai trạng thái màu. dp[c] là bóng hiện tại có màu $c$ (1 là đỏ). Mỗi bóng đỏ bị trừ lam và tăng số đỏ; cặp kề khác màu cộng a[i - 1].

for (int c = 0; c < 2; c++) {
    nd[c] = {LLONG_MIN, 0};
    for (int p = 0; p < 2; p++) {
        pair<ll, ll> v = {dp[p].first + (p != c ? a[i - 1] : 0) - (c ? lam : 0), dp[p].second + c};
        nd[c] = max(nd[c], v);
    }
}

Bước 2: chặt mức phạt như ví dụ đầu. Khoảng chặt tới $3 \cdot 10^9$: lợi ích lớn nhất của một bóng đỏ thêm là hai cặp kề, tối đa $2 \cdot 10^9$, cộng dư.

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

const int N = 2e5 + 5;
int n;
ll r, a[N];

pair<ll, ll> solve(ll lam) {
    pair<ll, ll> dp[2] = {{0, 0}, {-lam, 1}};
    for (int i = 2; i <= n; i++) {
        pair<ll, ll> nd[2];
        for (int c = 0; c < 2; c++) {
            nd[c] = {LLONG_MIN, 0};
            for (int p = 0; p < 2; p++) {
                pair<ll, ll> v = {dp[p].first + (p != c ? a[i - 1] : 0) - (c ? lam : 0), dp[p].second + c};
                nd[c] = max(nd[c], v);
            }
        }
        dp[0] = nd[0], dp[1] = nd[1];
    }
    return max(dp[0], dp[1]);
}

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

    cin >> n >> r;
    for (int i = 1; i < n; i++) cin >> a[i];
    r = min(r, n - r);
    ll l = 0, h = 3e9, res = 0;
    while (l <= h) {
        ll mid = (l + h) / 2;
        if (solve(mid).second >= r) res = mid, l = mid + 1;
        else h = mid - 1;
    }
    cout << solve(res).first + res * r << '\n';
}

ChạyInput5 2
3 8 2 6

Output19

Độ phức tạp: $O(N \log 3 \cdot 10^9)$.

Hai giới hạn

Có hai loại tài nguyên, mỗi loại giới hạn số lượng: phạt riêng $\lambda_a$ và $\lambda_b$. Khi đã cố định cả hai, mỗi đối tượng tự chọn phương án tốt nhất độc lập, $O(n)$. Chặt nhị phân $\lambda_a$ bên trong (để dùng không quá $a$), rồi $\lambda_b$ bên ngoài, tổng $O(n \log^2 C)$. Với giá trị thực, chặt theo số vòng cố định (50 vòng mỗi lớp) và chấp nhận sai số nhỏ của đề.

Cách lồng chỉ đúng khi bài vẫn lõm theo từng chiều khi chiều kia đã được nới lỏng; với xác suất, chọn độc lập và tổng tuyến tính như bài dưới, điều này thỏa.

Ví dụHai Loại Bóng Săn

Đề. $n \le 2000$ mục tiêu, có không quá $a$ bóng loại một (bắt với xác suất $p_i$) và $b$ bóng loại hai ($u_i$); mỗi mục tiêu nhận tối đa một bóng mỗi loại. Kỳ vọng số mục tiêu bắt được lớn nhất, sai số $10^{-4}$.

Lời giải. Hai giới hạn số bóng thì dùng hai mức phạt. Với hai mức phạt cố định, mỗi mục tiêu tự chọn phương án tốt nhất trong bốn, độc lập với nhau: không bóng, bóng một, bóng hai, cả hai ($p + u - pu$). Hai lớp chặt nhị phân trên đoạn $[0, 1]$.

Bước 1: đánh giá với hai mức phạt. Đếm luôn số bóng mỗi loại đã dùng.

double c1 = p[i] - la, c2 = u[i] - lb, c3 = p[i] + u[i] - p[i] * u[i] - la - lb;
if (c1 > best) best = c1, x = 1, y = 0;
if (c2 > best) best = c2, x = 0, y = 1;
if (c3 > best) best = c3, x = 1, y = 1;
v += best, ca += x, cb += y;

Bước 2: lớp trong. Với lb cố định, chặt la 50 vòng cho tới khi số bóng loại một không quá $A$, rồi trả $g + la \cdot A$.

for (int it = 0; it < 50; it++) {
    double mid = (lo + hi) / 2;
    eval(mid, lb, v, ca, cb);
    if (ca > A) lo = mid;
    else hi = mid;
}
eval(hi, lb, v, ca, cb);
return v + hi * A;

Bước 3: lớp ngoài chặt lb theo cùng cách, dựa trên số bóng loại hai mà inner báo về. Xác suất là số thực nên không có phá hòa chính xác; chặt theo số vòng cố định và lấy cận hi để số bóng không vượt giới hạn. Sai số còn lại dưới $10^{-4}$ đề cho phép.

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

int n, A, B;
double p[2005], u[2005];

void eval(double la, double lb, double &v, int &ca, int &cb) {
    v = 0, ca = cb = 0;
    for (int i = 0; i < n; i++) {
        double best = 0;
        int x = 0, y = 0;
        double c1 = p[i] - la, c2 = u[i] - lb, c3 = p[i] + u[i] - p[i] * u[i] - la - lb;
        if (c1 > best) best = c1, x = 1, y = 0;
        if (c2 > best) best = c2, x = 0, y = 1;
        if (c3 > best) best = c3, x = 1, y = 1;
        v += best, ca += x, cb += y;
    }
}

double inner(double lb, int &cb) {
    double lo = 0, hi = 1, v;
    int ca;
    for (int it = 0; it < 50; it++) {
        double mid = (lo + hi) / 2;
        eval(mid, lb, v, ca, cb);
        if (ca > A) lo = mid;
        else hi = mid;
    }
    eval(hi, lb, v, ca, cb);
    return v + hi * A;
}

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

    cin >> n >> A >> B;
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) cin >> u[i];
    double lo = 0, hi = 1;
    int cb;
    for (int it = 0; it < 50; it++) {
        double mid = (lo + hi) / 2;
        inner(mid, cb);
        if (cb > B) lo = mid;
        else hi = mid;
    }
    double ans = inner(hi, cb) + hi * B;
    cout << fixed << setprecision(10) << ans << '\n';
}

ChạyInput2 1 1
0.500 0.000
0.000 0.500

Output1.0000000000

$50 \cdot 50 \cdot n = 5 \cdot 10^6$ lượt đánh giá mục tiêu.