Bitmask DP

Trạng thái là tập

Quay lại bài phân công. Ta đánh số người và việc từ 0, vì bit thấp nhất của một số nguyên có chỉ số 0, và giao việc lần lượt cho người 0, 1, 2, cứ thế. Giả sử $k$ người đầu đã nhận xong việc, và các việc họ nhận tạo thành tập $S$ với $|S| = k$. Phần còn lại chỉ phụ thuộc $S$, nên trong mọi cách giao cho $k$ người đầu mà dùng đúng tập $S$, ta chỉ cần nhớ cách rẻ nhất. Đặt $\mathrm{dp}(S)$ là tổng chi phí nhỏ nhất khi giao các việc của $S$ cho $|S|$ người đầu tiên.

Người cuối cùng trong nhóm đó là người $|S| - 1$, và người ấy nhận một việc $j \in S$ nào đó. Bỏ cặp này đi thì $|S| - 1$ người còn lại giữ đúng các việc của $S \setminus \{j\}$. Thử mọi $j$:

Đáp án là $\mathrm{dp}(\{0, 1, \dots, n-1\})$. Tập $S$ được mã hóa bằng số nguyên mask: tập rỗng là 0, tập đầy đủ là (1 << n) - 1, $|S|$ là __builtin_popcount(mask), và bỏ việc $j$ khỏi tập là mask ^ (1 << j).

Chạy tay với $n = 3$. Người 0 làm việc 0, 1, 2 mất lần lượt 9, 2, 7; người 1 mất 6, 4, 3; người 2 mất 5, 8, 1. Với một việc, chỉ người 0 nhận: $\mathrm{dp}(\{0\}) = 9$, $\mathrm{dp}(\{1\}) = 2$, $\mathrm{dp}(\{2\}) = 7$. Với hai việc, người 1 nhận sau cùng: $\mathrm{dp}(\{0,1\}) = \min(2 + 6,\ 9 + 4) = 8$, và tương tự $\mathrm{dp}(\{0,2\}) = 12$, $\mathrm{dp}(\{1,2\}) = 5$. Với ba việc, người 2 nhận sau cùng: $\mathrm{dp}(\{0,1,2\}) = \min(5 + 5,\ 12 + 8,\ 8 + 1) = 9$.

Hình dưới cho thấy bảng dp. Mỗi ô ghi mask và dp của nó; tầng thứ $k$ là các tập có $k$ việc, đường xanh là cách giao rẻ nhất.

Mask 011 trong hình là tập $\{0, 1\}$ (bit 0 ở ngoài cùng bên phải). Đường đậm đi từ tập rỗng tới tập đầy đủ là một cách giao: người 0 nhận việc 1, người 1 nhận việc 0, người 2 nhận việc 2, tổng $2 + 6 + 1 = 9$.

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

ll n, c[20][20], dp[1 << 20];

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

    cin >> n;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++) cin >> c[i][j];
    for (ll mask = 1; mask < (1 << n); mask++) {
        ll k = __builtin_popcountll(mask);
        dp[mask] = 1e18;
        for (ll j = 0; j < n; j++)
            if ((mask >> j) & 1) dp[mask] = min(dp[mask], dp[mask ^ (1 << j)] + c[k - 1][j]);
    }
    cout << dp[(1 << n) - 1] << '\n';
}

ChạyInput3
9 2 7
6 4 3
5 8 1

Output9

Có $2^n$ trạng thái, mỗi trạng thái thử tối đa $n$ việc, nên tổng là $O(n \cdot 2^n)$: với $n = 20$ khoảng $2 \cdot 10^7$ phép tính và bảng 8 MB. Bảng không nhớ ai làm việc gì, chỉ nhớ việc nào đã dùng; và người đang xét không phải một chiều riêng, vì đó luôn là người thứ popcount(mask) - 1.

Ví dụGhép Cặp Tương Thích

Đề. Có $N \le 21$ người nhóm $A$ và $N$ người nhóm $B$; ma trận 0/1 cho biết cặp nào tương thích. Đếm số cách ghép hoàn hảo, mỗi người đúng một lần, chỉ dùng cặp tương thích, theo modulo $10^9 + 7$.

Lời giải. Đúng khuôn phân công, chỉ đổi “lấy min” thành “cộng số cách”. dp[mask] là số cách ghép $|mask|$ người đầu của nhóm $A$ với đúng các người của nhóm $B$ trong mask. Người $A$ thứ $k - 1$ (với $k$ là popcount) ghép với một $j \in$ mask tương thích: dp[mask] += dp[mask ^ (1 << j)]. $2^{21} \cdot 21 \approx 4{,}4 \cdot 10^7$ phép, bảng $2^{21}$ số. Duyệt hết $N!$ hoán vị ở đây là $5 \cdot 10^{19}$.

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

const ll MOD = 1e9 + 7;
ll n, a[21][21], dp[1 << 21];

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

    cin >> n;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++) cin >> a[i][j];
    dp[0] = 1;
    for (ll mask = 1; mask < (1 << n); mask++) {
        ll k = __builtin_popcountll(mask);
        for (ll j = 0; j < n; j++)
            if (((mask >> j) & 1) && a[k - 1][j]) dp[mask] = (dp[mask] + dp[mask ^ (1 << j)]) % MOD;
    }
    cout << dp[(1 << n) - 1] << '\n';
}

ChạyInput3
1 1 0
0 1 1
1 0 1

Output2

Ví dụChuyến Thang Máy

Đề. Có $N \le 20$ người, người $i$ nặng $w_i$; thang máy chở tối đa $X$ mỗi lượt, $w_i \le X \le 10^9$. Chia mọi người vào ít lượt nhất.

Lời giải. Ta không cần biết ai đi lượt nào, chỉ cần biết tập người đã xếp, số lượt đã dùng và lượt đang mở đã chở bao nhiêu. Hai con số cuối không so sánh trực tiếp được: một cách dùng ít lượt hơn nhưng lượt cuối đầy, cách khác nhiều lượt hơn nhưng lượt cuối còn trống. Ta cho thứ tự từ điển phân xử: số lượt trước, tải lượt cuối sau. Xếp người lần lượt theo một thứ tự nào đó, mỗi người vào lượt đang mở nếu còn chỗ, nếu không thì mở lượt mới; dp[mask] là cặp (số lượt, tải lượt cuối) nhỏ nhất theo thứ tự từ điển trong mọi thứ tự xếp tập mask, với dp[0] = (1, 0). Chuyển: chọn người $i$ xếp sau cùng, từ cặp $(r, l)$ của mask ^ (1 << i) ta được $(r, l + w_i)$ nếu $l + w_i \le X$, ngược lại $(r + 1, w_i)$.

Giữ cặp nhỏ nhất là đủ vì phép “thêm một người” giữ nguyên thứ tự từ điển: cùng số lượt mà tải nhỏ hơn thì sau khi thêm vẫn không tệ hơn, ít lượt hơn thì sau khi thêm nhiều nhất bằng số lượt của bên kia với tải chỉ $w_i$. Và đáp án đạt được: với cách chia tối ưu, xếp người theo từng lượt một thì quá trình dùng không quá số lượt ấy. $N \cdot 2^N = 2 \cdot 10^7$ phép. Với ví dụ, $\{2, 3, 5\}$ và $\{6, 4\}$ cho hai lượt.

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

ll n, X, w[20];
pair<ll, ll> dp[1 << 20];

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

    cin >> n >> X;
    for (ll i = 0; i < n; i++) cin >> w[i];
    dp[0] = {1, 0};
    for (ll mask = 1; mask < (1 << n); mask++) {
        dp[mask] = {n + 1, 0};
        for (ll i = 0; i < n; i++) {
            if (!((mask >> i) & 1)) continue;
            pair<ll, ll> cur = dp[mask ^ (1 << i)];
            if (cur.second + w[i] <= X) cur.second += w[i];
            else cur = {cur.first + 1, w[i]};
            dp[mask] = min(dp[mask], cur);
        }
    }
    cout << dp[(1 << n) - 1].first << '\n';
}

ChạyInput5 10
2 3 5 6 4

Output2

Kéo, đẩy, đệ quy

Mỗi bước chuyển thêm một phần tử vào tập, tức là bật thêm một bit, nên số nguyên tăng lên. Vì thế khi duyệt mask từ 0 lên (1 << n) - 1, lúc tới mask thì mọi tập con thật sự của nó đã được tính xong: bỏ đi một bit luôn cho số nhỏ hơn. Ta không phải tìm thứ tự tính riêng, một vòng for thường là đủ.

Các chương trình trên viết theo kiểu kéo (pull): tại mask, nhìn lại các trạng thái đứng trước để tính dp[mask]. Kiểu đẩy (push) làm ngược lại: khi tới mask thì dp[mask] đã chốt, từ đó cập nhật các trạng thái đứng sau. Với bài phân công:

for (ll mask = 0; mask < (1 << n) - 1; mask++) {
    if (dp[mask] == 1e18) continue;
    ll k = __builtin_popcountll(mask);
    for (ll j = 0; j < n; j++) {
        if ((mask >> j) & 1) continue;
        ll nx = mask | (1 << j);
        dp[nx] = min(dp[nx], dp[mask] + c[k][j]);
    }
}

Hai kiểu cho cùng kết quả, và khác nhau ở hai chỗ khi cài. Thứ nhất, kiểu đẩy phải khởi tạo mọi ô (trừ ô xuất phát) bằng “vô cùng” và chỉ đẩy từ ô đã tới được; quên dòng continue thì INF + chi phí có thể tràn số hoặc tạo ra một giá trị giả trông như hợp lệ. Thứ hai là chỉ số người: lúc đẩy, mask có $k$ bit nghĩa là $k$ người đã có việc nên người nhận việc mới là người $k$; lúc kéo, mask mới có $k$ bit và người vừa nhận việc là người $k - 1$. Kiểu kéo hợp khi công thức tự nhiên là “phần tử thêm cuối cùng là ai”. Kiểu đẩy hợp khi điều kiện chuyển phụ thuộc vào cả mask hiện tại, ví dụ chỉ được thêm việc $v$ khi mọi việc phải làm trước $v$ đã nằm trong mask.

Cách thứ ba là đệ quy có nhớ: solve(mask) gọi solve của các mask nhỏ hơn và lưu kết quả. Cách này chỉ tính những trạng thái thật sự được gọi tới, nên có lợi khi từ trạng thái đầu chỉ tới được một phần nhỏ của $2^n$ trạng thái, ví dụ trò nhảy sỏi trên 12 ô. Khi gần như mọi mask đều tới được thì vòng lặp nhanh hơn và không tốn chi phí gọi hàm.

Ví dụCác Thứ Tự Hợp Lệ

Đề. Có $N \le 16$ công việc và $M$ quan hệ “$x$ phải đứng trước $y$”, không tạo chu trình. Đếm số thứ tự xếp mọi công việc thỏa mọi quan hệ.

Lời giải. dp[mask] là số cách xếp tập công việc mask thành một tiền tố hợp lệ của thứ tự. Một tiền tố nhận thêm công việc $v$ khi và chỉ khi mọi công việc phải đứng trước $v$ đã nằm trong tiền tố; gọi tập đó là pre[v], điều kiện là (pre[v] & mask) == pre[v]. Điều kiện phụ thuộc mask hiện tại, nên viết kiểu đẩy là tự nhiên. Đáp án tới $16! \approx 2 \cdot 10^{13}$, vừa ll; chi phí $N \cdot 2^N \approx 10^6$. Với ví dụ, 2 phải đứng trước 3 và 4, 1 phải đứng trước 3: có 5 thứ tự.

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

ll n, m, pre[16], dp[1 << 16];

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

    cin >> n >> m;
    for (ll i = 0; i < m; i++) {
        ll x, y;
        cin >> x >> y;
        pre[y - 1] |= 1LL << (x - 1);
    }
    dp[0] = 1;
    for (ll mask = 0; mask < (1 << n); mask++) {
        if (!dp[mask]) continue;
        for (ll v = 0; v < n; v++)
            if (!((mask >> v) & 1) && (pre[v] & mask) == pre[v]) dp[mask | (1 << v)] += dp[mask];
    }
    cout << dp[(1 << n) - 1] << '\n';
}

ChạyInput4 3
1 3
2 3
2 4

Output5

Thêm đỉnh cuối

Không phải bài nào cũng chỉ cần một tập. Bài toán người bán hàng (TSP, Travelling Salesman Problem): có $n$ đỉnh đánh số từ 0, chi phí đi thẳng từ $u$ tới $v$ là $d_{u,v}$ (không nhất thiết bằng $d_{v,u}$). Xuất phát tại đỉnh 0, đi qua mọi đỉnh đúng một lần rồi trở về 0, tổng chi phí nhỏ nhất. Thử mọi thứ tự là $(n-1)!$ cách; $n = 16$ đã là $1{,}3 \cdot 10^{12}$.

Thử bê nguyên cách ở mục trước: $\mathrm{dp}(S)$ là chi phí nhỏ nhất của đường đi từ 0 qua đúng các đỉnh của $S$. Công thức chuyển không viết được, vì bước tiếp theo tốn $d_{\text{đỉnh cuối},\, v}$ mà $\mathrm{dp}(S)$ không cho biết đỉnh cuối là đỉnh nào. Hai đường đi qua cùng tập $S$ nhưng dừng ở hai đỉnh khác nhau có tương lai khác nhau, nên không gộp được. Đặt $\mathrm{dp}(S, v)$ là chi phí nhỏ nhất của đường đi xuất phát từ 0, đi qua đúng các đỉnh của $S$, mỗi đỉnh một lần, và dừng ở $v \in S$. Đỉnh ngay trước $v$ là một $u \in S \setminus \{v\}$:

Các trạng thái không tới được (ví dụ mask không chứa đỉnh 0) giữ giá trị vô cùng. Đáp án là $\min_{v \ne 0} \bigl( \mathrm{dp}(\text{đủ}, v) + d_{v,0} \bigr)$, trong đó phần cộng thêm là chặng quay về. Quy tắc chọn trạng thái rút ra từ hai bài: giữ đúng những gì tương lai cần biết về quá khứ. Thiếu một thông tin thì công thức sai; thừa một thông tin thì bảng to và chậm hơn mà không thêm được gì.

Hình dưới điền bảng dp[mask][v] theo kiểu đẩy: ô cam vừa được cập nhật từ ô xanh. Cuối cùng là chu trình trên đồ thị.

Trong hình, dp[5][2] là trạng thái “đã qua các đỉnh 0 và 2 (mask 0101), đang đứng ở đỉnh 2”; từ đó đi tiếp sang đỉnh 1 cho trạng thái dp[7][1]. Chương trình dưới viết theo kiểu đẩy và in thêm đường đi. Bảng không lưu đỉnh đứng trước, nên truy vết làm bằng cách lùi: từ $(\text{đủ}, v)$, tìm $u$ thỏa $\mathrm{dp}(S \setminus \{v\}, u) + d_{u,v} = \mathrm{dp}(S, v)$; mỗi bước tốn $O(n)$, rẻ hơn giữ thêm một mảng cha cùng cỡ với bảng. Ví dụ có 4 đỉnh, đường ngắn nhất là $0 \to 2 \to 1 \to 3 \to 0$ với $3 + 6 + 2 + 5 = 16$.

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

ll n, d[16][16], dp[1 << 16][16];

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

    cin >> n;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++) cin >> d[i][j];
    ll full = (1 << n) - 1;
    for (ll mask = 0; mask <= full; mask++)
        for (ll v = 0; v < n; v++) dp[mask][v] = 1e18;
    dp[1][0] = 0;
    for (ll mask = 1; mask <= full; mask++)
        for (ll v = 0; v < n; v++) {
            if (dp[mask][v] == 1e18) continue;
            for (ll u = 0; u < n; u++)
                if (!((mask >> u) & 1))
                    dp[mask | (1 << u)][u] = min(dp[mask | (1 << u)][u], dp[mask][v] + d[v][u]);
        }
    ll best = 1e18, e = 0;
    for (ll v = 1; v < n; v++)
        if (dp[full][v] + d[v][0] < best) {
            best = dp[full][v] + d[v][0];
            e = v;
        }
    cout << best << '\n';
    vector<ll> path;
    ll mask = full, v = e;
    while (v != 0) {
        path.push_back(v);
        ll pm = mask ^ (1 << v);
        for (ll u = 0; u < n; u++)
            if (((pm >> u) & 1) && dp[pm][u] + d[u][v] == dp[mask][v]) {
                mask = pm;
                v = u;
                break;
            }
    }
    path.push_back(0);
    reverse(path.begin(), path.end());
    for (ll x : path) cout << x << ' ';
    cout << 0 << '\n';
}

ChạyInput4
0 7 3 9
4 0 4 2
3 6 0 8
5 2 5 0

Output16
0 2 1 3 0

Có $2^n \cdot n$ trạng thái, mỗi trạng thái thử tối đa $n$ đỉnh kế tiếp: $O(2^n n^2)$ thời gian và $O(2^n n)$ bộ nhớ. Với $n = 16$ đó là $1{,}7 \cdot 10^7$ phép; với $n = 20$ là $4{,}2 \cdot 10^8$, và riêng bảng int đã 84 MB.

Muốn đếm số đường đi, thay min bằng phép cộng và đặt dp[1][0] = 1. Muốn đường đi tự do, điểm đầu tùy ý và không quay về, khởi tạo dp[1 << v][v] = 0 cho mọi v và lấy $\min_v \mathrm{dp}(\text{đủ}, v)$.

Kiểu của bảng cũng ảnh hưởng, vì bảng này rất lớn:

Bảng long long chậm hơn bảng int khoảng 1,2 lần và tốn gấp đôi bộ nhớ. Quy tắc: tổng chi phí vừa int thì dùng int, nhất là khi bảng cỡ trăm MB.

Ví dụChu Trình Qua Các Trạm Bay

Đề. Có $N \le 17$ trạm trong không gian, đi từ $i$ tới $j$ tốn $|X_i - X_j| + |Y_i - Y_j| + \max(0, Z_j - Z_i)$. Xuất phát ở trạm 1, ghé mọi trạm ít nhất một lần (được ghé lại), rồi quay về trạm 1. In tổng chi phí nhỏ nhất.

Lời giải. Đề cho phép ghé lại, nhưng chi phí này thỏa bất đẳng thức tam giác: đi thẳng $i \to k$ không đắt hơn đi vòng $i \to j \to k$, vì phần $|X|$, $|Y|$ thỏa bất đẳng thức tam giác thường, còn phần leo cao $\max(0, Z_k - Z_i) \le \max(0, Z_j - Z_i) + \max(0, Z_k - Z_j)$. Vậy mọi lần ghé lại đều bỏ được mà không tốn thêm, và bài đúng là TSP: mỗi trạm đúng một lần, có chặng quay về trạm 1. $2^{17} \cdot 17^2 \approx 3{,}8 \cdot 10^7$ phép.

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

ll n, x[17], y[17], z[17], d[17][17], dp[1 << 17][17];

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

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i];
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++) d[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0LL, z[j] - z[i]);
    ll full = (1 << n) - 1;
    for (ll mask = 0; mask <= full; mask++)
        for (ll v = 0; v < n; v++) dp[mask][v] = 1e18;
    dp[1][0] = 0;
    for (ll mask = 1; mask <= full; mask++)
        for (ll v = 0; v < n; v++) {
            if (dp[mask][v] == 1e18) continue;
            for (ll u = 0; u < n; u++)
                if (!((mask >> u) & 1))
                    dp[mask | (1 << u)][u] = min(dp[mask | (1 << u)][u], dp[mask][v] + d[v][u]);
        }
    ll ans = 1e18;
    for (ll v = 1; v < n; v++) ans = min(ans, dp[full][v] + d[v][0]);
    cout << ans << '\n';
}

ChạyInput2
0 0 0
2 -1 4

Output10

Chia nhóm

Có những bài mà bước cuối cùng không thêm một phần tử mà tách cả một nhóm. Ví dụ: $n$ vật khối lượng $w_i$, chia thành các nhóm sao cho tổng khối lượng mỗi nhóm không vượt $X$; đếm số cách chia, không phân biệt thứ tự các nhóm.

Đặt $\mathrm{ways}(S)$ là số cách chia tập $S$. Nhóm cuối cùng là một tập con $T \subseteq S$ hợp lệ, phần còn lại $S \setminus T$ được chia tự do. Nếu cộng $\mathrm{ways}(S \setminus T)$ trên mọi $T$, một cách chia thành $g$ nhóm bị đếm $g!$ lần, mỗi lần ứng với một thứ tự chọn nhóm cuối. Cách sửa là bắt buộc nhóm tách ra phải chứa phần tử nhỏ nhất của $S$, gọi là $p$. Mỗi cách chia có đúng một nhóm chứa $p$, nên mỗi cách chia chỉ sinh ra đúng một lần:

Với mask là tập $S$ và low là bit thấp nhất của nó, nhóm $T$ gồm low cộng một tập con bất kỳ của rest = mask ^ low, duyệt bằng vòng s = (s - 1) & rest của bài 14. Dùng dạng đầy đủ của vòng lặp, vì tập con rỗng của rest ứng với nhóm chỉ có một mình low, và nó phải được xử lý trước khi thoát.

Trong hình, bấm bit của mask để chọn tập; mỗi hàng $T$ là một nhóm chứa bit thấp nhất.

Cố định low còn cắt đi một nửa chi phí. Một mask có $k$ bit chỉ còn $2^{k-1}$ nhóm thay cho $2^k$, nên tổng trên mọi mask chỉ còn khoảng một nửa của $3^n$, đúng ra là $(3^n - 1)/2$. Với $n = 16$ đó là $2 \cdot 10^7$, với $n = 18$ là $2 \cdot 10^8$, còn $n = 20$ đã là $1{,}7 \cdot 10^9$, quá chậm. Chương trình dưới tính sẵn sum[mask], tổng khối lượng của mỗi tập, nên kiểm tra một nhóm hợp lệ tốn $O(1)$.

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

ll n, X, w[16], sum[1 << 16], ways[1 << 16];

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

    cin >> n >> X;
    for (ll i = 0; i < n; i++) cin >> w[i];
    ll full = (1 << n) - 1;
    for (ll mask = 1; mask <= full; mask++) sum[mask] = sum[mask & (mask - 1)] + w[__builtin_ctzll(mask)];
    ways[0] = 1;
    for (ll mask = 1; mask <= full; mask++) {
        ll low = mask & -mask, rest = mask ^ low;
        for (ll s = rest;; s = (s - 1) & rest) {
            if (sum[s | low] <= X) ways[mask] += ways[mask ^ (s | low)];
            if (s == 0) break;
        }
    }
    cout << ways[full] << '\n';
}

ChạyInput4 9
6 4 3 5

Output6

Kiểm tay với khối lượng 6, 4, 3, 5 và $X = 9$. Cặp hợp lệ chỉ có $\{6, 3\}$, $\{4, 3\}$, $\{4, 5\}$, $\{3, 5\}$; không có nhóm ba hợp lệ. Bốn nhóm đơn cho 1 cách, một cặp cùng hai nhóm đơn cho 4 cách, hai cặp chỉ có $\{6, 3\}$ cùng $\{4, 5\}$. Tổng 6. Nếu cho $X$ lớn để mọi nhóm đều hợp lệ, chương trình in 15, là số Bell $B_4$.

Ví dụPhân Nhóm Tối Đa Điểm

Đề. Có $N \le 16$ thành viên; hai người $i, j$ cùng nhóm thì nhận $a_i[j]$ điểm (ma trận đối xứng, có thể âm, $|a_i[j]| \le 10^9$). Chia mọi người thành các nhóm không rỗng để tổng điểm lớn nhất.

Lời giải. Điểm của một nhóm chỉ phụ thuộc tập thành viên: $\mathrm{score}(T)$ là tổng $a_i[j]$ trên mọi cặp $i < j$ trong $T$. Tính score[mask] từ score[mask & (mask - 1)], cộng thêm điểm giữa thành viên thấp nhất và mọi thành viên còn lại, $O(N)$ mỗi mask. Rồi chia nhóm đúng khuôn trên, thay đếm bằng lấy max: $\mathrm{dp}(S) = \max (\mathrm{dp}(S \setminus T) + \mathrm{score}(T))$ trên các nhóm $T$ chứa phần tử nhỏ nhất của $S$. Điểm âm không phá được công thức vì ta xét mọi $T$, không tham lam gộp nhóm; mỗi người một nhóm cho 0, nên đáp án không âm. Chi phí $(3^{16} - 1)/2 \approx 2 \cdot 10^7$; điểm tới $1{,}2 \cdot 10^{11}$ nên dùng ll. Với ví dụ, nhóm $\{1, 2\}$ cho 5 và người 3 đứng riêng.

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

ll n, a[16][16], sc[1 << 16], dp[1 << 16];

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

    cin >> n;
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++) cin >> a[i][j];
    ll full = (1 << n) - 1;
    for (ll mask = 1; mask <= full; mask++) {
        ll v = __builtin_ctzll(mask), rest = mask & (mask - 1);
        sc[mask] = sc[rest];
        for (ll u = 0; u < n; u++)
            if ((rest >> u) & 1) sc[mask] += a[v][u];
    }
    for (ll mask = 1; mask <= full; mask++) {
        ll low = mask & -mask, rest = mask ^ low;
        dp[mask] = -1e18;
        for (ll s = rest;; s = (s - 1) & rest) {
            dp[mask] = max(dp[mask], dp[mask ^ (s | low)] + sc[s | low]);
            if (s == 0) break;
        }
    }
    cout << dp[full] << '\n';
}

ChạyInput3
0 5 -4
5 0 2
-4 2 0

Output5

Mask và vị trí

Đôi khi mask chỉ là một phần của trạng thái, phần còn lại là vị trí đang xét trong một dãy. Ví dụ: đếm xâu độ dài $L$ trên bảng chữ cái $k$ chữ ($k \le 10$) sao cho mỗi chữ cái xuất hiện ít nhất một lần. Đặt dp[i][mask] là số xâu độ dài $i$ mà tập các chữ đã xuất hiện đúng bằng mask. Thêm chữ $c$ vào cuối cho tập chữ mask | (1 << c), và đáp án là dp[L][(1 << k) - 1]. Lớp $i + 1$ chỉ lấy từ lớp $i$, nên chương trình giữ hai mảng f, g thay vì cả bảng. Thời gian $O(L \cdot k \cdot 2^k)$.

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

ll L, k, f[1 << 10], g[1 << 10];

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

    cin >> L >> k;
    f[0] = 1;
    for (ll i = 0; i < L; i++) {
        for (ll mask = 0; mask < (1 << k); mask++) g[mask] = 0;
        for (ll mask = 0; mask < (1 << k); mask++)
            for (ll c = 0; c < k; c++) g[mask | (1 << c)] += f[mask];
        for (ll mask = 0; mask < (1 << k); mask++) f[mask] = g[mask];
    }
    cout << f[(1 << k) - 1] << '\n';
}

ChạyInput10 5

Output5103000

Kết quả khớp công thức bao hàm loại trừ $5^{10} - 5 \cdot 4^{10} + 10 \cdot 3^{10} - 10 \cdot 2^{10} + 5 = 5\,103\,000$. Bài nào có sẵn công thức đóng để đối chiếu như vậy thì nên kiểm chương trình trên vài ví dụ nhỏ trước khi nộp.

Mask không nhất thiết là “tập đã dùng”. Ba vai trò hay gặp khác:

• Tập đã phủ. Chọn các gói, mỗi gói phủ một tập tính năng, để phủ đủ mọi tính năng với tổng giá nhỏ nhất. Chuyển bằng phép hợp: dp[mask | key[i]] nhận dp[mask] + cost[i]. Vẫn duyệt mask tăng dần được, vì mask | key[i] >= mask.
• Vector chẵn lẻ. Tích các số là số chính phương khi mọi số mũ nguyên tố đều chẵn. Mỗi bit của mask ghi tính chẵn lẻ số mũ của một nguyên tố, và thêm một số là phép XOR với mask của số đó.
• Cửa sổ trượt. Đếm hoán vị thỏa $|P_i - i| \le M$: khi điền vị trí $i$ chỉ các giá trị trong $[i - M, i + M]$ dùng được, nên mask $2M + 1$ bit ghi giá trị nào của cửa sổ đã dùng, và dịch phải một bit mỗi khi sang vị trí kế.

Bao nhiêu phần tử thì còn dùng được. Trước khi cài, tính hai con số: số phép tính (số trạng thái nhân số chuyển của mỗi trạng thái) và số byte của bảng. Với một giây ta chạy được cỡ $10^8$ phép đơn giản: $n \cdot 2^n$ ở $n = 20$ là $2 \cdot 10^7$, thoải mái; $n^2 \cdot 2^n$ ở $n = 20$ là $4{,}2 \cdot 10^8$, sát giới hạn; $3^n$ ở $n = 18$ là $3{,}9 \cdot 10^8$ (một nửa nếu cố định phần tử nhỏ nhất). Về bộ nhớ, $2^{20} \cdot 20$ số int là 84 MB và gấp đôi với long long. Khi $n$ quá lớn cho $2^n$, hướng khác là chia đôi tập (bài 10); khi cần tổng trên mọi tập con thì dùng SOS DP (bài 46); khi mask là một hàng của lưới thì đó là quy hoạch động profile (bài 44). Duyệt các bit đang tắt của mask mà không xét cả $n$ bit: for (ll r = full ^ mask; r; r &= r - 1) { ll j = __builtin_ctzll(r); ... }.