Khóa học CTDL và GT

Bài 28.3. Bài toán ghép cặp tối ưu với DP Bitmask

Trong chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật, chúng ta đã đi qua nhiều kỹ thuật mạnh mẽ để giải quyết các vấn đề phức tạp. Hôm nay, chúng ta sẽ khám phá một sự kết hợp thú vị và cực kỳ hữu ích: Quy hoạch động (DP) cùng với Bitmask (Mặt nạ bit) để giải quyết một lớp bài toán quen thuộc: Bài toán ghép cặp tối ưu.

Bài toán ghép cặp xuất hiện ở khắp mọi nơi, từ việc phân công công việc, ghép đôi trong một buổi tiệc, cho đến việc tìm đường đi ngắn nhất trong một đồ thị đặc biệt. Khi mục tiêu là tìm ra cách ghép cặp sao cho tổng giá trị (chi phí) là tối thiểu hoặc tối đa, chúng ta đối mặt với bài toán ghép cặp tối ưu.

Vấn đề đặt ra: Ghép cặp tối ưu trên tập hợp nhỏ

Xét một bài toán điển hình: Bạn có N vật thể (ví dụ: công việc, người, điểm ảnh), và bạn biết "chi phí" hoặc "giá trị" khi ghép cặp bất kỳ hai vật thể i và j nào đó. Yêu cầu là tìm cách ghép cặp các vật thể này sao cho tổng chi phí/giá trị là tối ưu (min hoặc max).

Nếu N nhỏ, chẳng hạn N <= 20, chúng ta có thể nghĩ đến việc thử mọi cách ghép cặp. Nhưng số cách ghép cặp hoàn hảo (khi N chẵn và ghép hết N vật thể thành N/2 cặp) tăng rất nhanh theo N. Cách tiếp cận vét cạn (brute force) sẽ nhanh chóng trở nên bất khả thi.

Đó là lúc chúng ta cần đến sức mạnh của Quy hoạch động. Tuy nhiên, để áp dụng DP cho các bài toán trên tập hợp con, việc theo dõi những phần tử nào đã được sử dụng là tối quan trọng. DP truyền thống thường chỉ đếm số lượng phần tử đã sử dụng, điều này không đủ để phân biệt các tập hợp con khác nhau có cùng kích thước nhưng chứa các phần tử khác nhau. Đây chính là nơi Bitmask tỏa sáng.

Sức mạnh của Bitmask trong DP

Bitmask là một kỹ thuật sử dụng một số nguyên để biểu diễn một tập hợp con của các phần tử. Nếu chúng ta có N phần tử được đánh số từ 0 đến N-1, một số nguyên mask có thể biểu diễn một tập hợp con bằng cách: bit thứ i của mask là 1 nếu phần tử i nằm trong tập hợp con, và là 0 nếu ngược lại.

Ví dụ với N=4:

• Mask 0 (binary 0000) biểu diễn tập hợp rỗng {}.
• Mask 1 (binary 0001) biểu diễn tập hợp {0}.
• Mask 3 (binary 0011) biểu diễn tập hợp {0, 1}.
• Mask 15 (binary 1111) biểu diễn tập hợp {0, 1, 2, 3} (tất cả các phần tử).

Sử dụng Bitmask, chúng ta có thể biểu diễn mọi tập hợp con của N phần tử bằng các số nguyên từ 0 đến 2^N - 1. Điều này cho phép chúng ta định nghĩa trạng thái DP dựa trên tập hợp con các phần tử đã được xử lý.

Công thức DP Bitmask cho bài toán ghép cặp

Chúng ta thường định nghĩa trạng thái DP như sau:

dp[mask] là giá trị (chi phí tối thiểu hoặc giá trị tối đa) đạt được khi đã xử lý (ghép cặp) chính xác các phần tử có bit tương ứng bằng 1 trong mask.

Bài toán ghép cặp tối ưu thường yêu cầu ghép cặp tất cả N phần tử khi N chẵn. Chúng ta sẽ xây dựng dp[mask] từ các trạng thái nhỏ hơn.

Xét một trạng thái mask bất kỳ. Để đạt được trạng thái này bằng cách ghép cặp, cặp cuối cùng được thêm vào phải là hai phần tử i và j nào đó mà cả i và j đều có bit 1 trong mask. Trước khi thêm cặp (i, j), chúng ta phải ở trong trạng thái mask bỏ đi hai phần tử i và j, tức là trạng thái mask ^ (1 << i) ^ (1 << j).

Để tránh việc tính toán trùng lặp và đảm bảo quá trình chuyển trạng thái là có thứ tự, chúng ta thường chọn một phần tử cố định trong tập hợp con hiện tại (mask) để làm điểm neo. Cách phổ biến là chọn phần tử có chỉ số nhỏ nhất vẫn còn trong tập hợp con (mask). Giả sử i là chỉ số nhỏ nhất sao cho bit thứ i của mask là 1. Phần tử i này bắt buộc phải được ghép cặp với một phần tử khác j trong cùng tập hợp con (mask).

Công thức chuyển trạng thái cho bài toán cực tiểu hóa chi phí khi ghép cặp tất cả các phần tử trong mask (N phải chẵn):

dp[mask] = min(dp[mask ^ (1 << i) ^ (1 << j)] + cost[i][j])

với:

• i là chỉ số nhỏ nhất sao cho bit thứ i của mask là 1.
• j là bất kỳ chỉ số nào khác i sao cho bit thứ j của mask là 1.
• cost[i][j] là chi phí khi ghép cặp i và j.

Trường hợp cơ sở: dp[0] = 0 (tập hợp rỗng có chi phí 0).

Kết quả cuối cùng: dp[(1 << N) - 1] (mask với tất cả N bit đều là 1, biểu diễn tập hợp gồm tất cả N phần tử).

Quá trình tính toán sẽ đi từ các mask có ít bit 1 đến các mask có nhiều bit 1.

Độ phức tạp: Có 2^N trạng thái. Với mỗi trạng thái mask, chúng ta tìm phần tử i nhỏ nhất (Mất O(N) hoặc O(1) với trick bitwise mask & -mask). Sau đó, chúng ta lặp qua O(N) phần tử j khác để ghép cặp với i. Tổng độ phức tạp: O(N 2^N). Với N=20, 2^20 khoảng 1 triệu, `20 2^20` khoảng 20 triệu phép tính, hoàn toàn khả thi trong giới hạn thời gian.

Ví dụ 1: Ghép cặp hoàn hảo với tổng chi phí nhỏ nhất

Bài toán: Cho N điểm (N chẵn), biết chi phí ghép cặp giữa mỗi cặp điểm (i, j) là C[i][j]. Tìm cách ghép cặp N điểm thành N/2 cặp sao cho tổng chi phí là nhỏ nhất.

Input: Số nguyên N (chẵn, <= 20) và ma trận chi phí C[i][j] kích thước N x N.

Output: Tổng chi phí nhỏ nhất.

Phân tích:

• Đây chính xác là bài toán ghép cặp hoàn hảo trên đồ thị đầy đủ có trọng số.
• Chúng ta cần ghép cặp tất cả N điểm.
• Sử dụng DP Bitmask: dp[mask] là chi phí nhỏ nhất để ghép cặp các điểm trong tập hợp con biểu diễn bởi mask.
• Vì chúng ta ghép cặp từng đôi, nên mask sẽ luôn có số lượng bit 1 là chẵn.

Mã C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

int cost[20][20]; // Ma trận chi phí, N <= 20
int dp[1 << 20]; // dp[mask]

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Đọc ma trận chi phí
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> cost[i][j];
        }
    }

    // Khởi tạo DP
    // dp[mask] = INF cho tất cả các mask trừ dp[0]
    for (int i = 0; i < (1 << n); ++i) {
        dp[i] = INF;
    }
    dp[0] = 0; // Trạng thái không có phần tử nào đã ghép cặp có chi phí 0

    // Tính toán DP
    // Duyệt qua tất cả các mask từ 0 đến 2^n - 1
    for (int mask = 0; mask < (1 << n); ++mask) {
        // Chỉ xét các mask có số bit 1 chẵn, vì ta ghép cặp từng đôi
        if (__builtin_popcount(mask) % 2 != 0) {
            continue;
        }

        // Nếu dp[mask] vẫn là INF, nghĩa là trạng thái này không thể đạt được
        // hoặc đã được tính toán thông qua một đường dẫn khác (nhưng ở đây ta duyệt tăng dần mask)
        // if (dp[mask] == INF) continue; // Không cần thiết khi duyệt mask tăng dần

        // Tìm phần tử có chỉ số nhỏ nhất trong mask
        int i = -1;
        for (int bit = 0; bit < n; ++bit) {
            if ((mask >> bit) & 1) {
                i = bit;
                break; // Tìm thấy bit 1 đầu tiên (nhỏ nhất)
            }
        }

        // Nếu mask rỗng (i == -1), bỏ qua (đã xử lý dp[0])
        if (i == -1) {
            continue;
        }

        // Ghép cặp phần tử i với các phần tử j khác trong mask
        for (int j = i + 1; j < n; ++j) { // Chỉ xét j > i để tránh trùng lặp cặp (i, j) và (j, i)
            if ((mask >> j) & 1) { // Nếu phần tử j cũng có trong mask
                // Tính mask mới sau khi loại bỏ i và j
                int next_mask = mask ^ (1 << i) ^ (1 << j);

                // Cập nhật trạng thái dp[mask]
                // dp[mask] có thể được đạt tới bằng cách ghép cặp (i, j) từ trạng thái next_mask
                if (dp[next_mask] != INF) { // Đảm bảo trạng thái trước đó có thể đạt được
                     dp[mask] = min(dp[mask], dp[next_mask] + cost[i][j]);
                }
            }
        }
    }

    // Kết quả là dp của mask có tất cả các bit là 1
    cout << dp[(1 << n) - 1] << endl;

    return 0;
}

Giải thích mã:

1. Includes và Khởi tạo:

   • Sử dụng vector, algorithm, limits cho các thao tác thông thường.
   • cost[20][20] lưu ma trận chi phí.
   • dp[1 << 20] là mảng DP. Kích thước 1 << 20 (tức 2^20) là đủ cho N=20.
   • INF dùng để biểu diễn giá trị vô cùng lớn, cho bài toán cực tiểu.
   • ios_base::sync_with_stdio(false); cin.tie(NULL); tăng tốc nhập/xuất.
   • Đọc N và ma trận cost.
   • Khởi tạo tất cả dp[mask] về INF, trừ dp[0] là 0.

2. Vòng lặp DP:

   • Lặp qua tất cả các mask từ 0 đến (1 << n) - 1. Điều này đảm bảo chúng ta tính DP theo thứ tự các tập hợp con có kích thước tăng dần.
   • __builtin_popcount(mask) đếm số bit 1 trong mask. Ta chỉ quan tâm đến các mask có số bit 1 chẵn vì mỗi bước ta thêm một cặp (2 phần tử).
   • Tìm i, chỉ số nhỏ nhất của phần tử có trong mask. Vòng lặp for (int bit = 0; bit < n; ++bit) làm điều này. Cách tối ưu hơn là dùng int i = __builtin_ctz(mask); (đếm số bit 0 liên tiếp từ phải sang) hoặc int i = log2(mask & -mask); nhưng vòng lặp đơn giản dễ hiểu hơn.
   • Nếu i == -1, mask rỗng (chỉ xảy ra với mask = 0, đã xử lý cơ sở).
   • Lặp qua j lớn hơn i. Lý do chỉ xét j > i là để mỗi cặp (i, j) chỉ được xét một lần khi i là phần tử nhỏ nhất trong cặp đó. Nếu j cũng có trong mask ((mask >> j) & 1), ta coi i được ghép với j.
   • next_mask = mask ^ (1 << i) ^ (1 << j): Đây là mask biểu diễn tập hợp con ban đầu mask sau khi đã bỏ đi phần tử i và j. Phép XOR (^) dùng để "lật bit".
   • dp[mask] = min(dp[mask], dp[next_mask] + cost[i][j]);: Công thức chuyển trạng thái. Chi phí để xử lý tập mask có thể là chi phí để xử lý tập next_mask cộng thêm chi phí ghép i và j. Ta lấy giá trị nhỏ nhất trong tất cả các lựa chọn ghép i với một j khác trong mask.

3. Kết quả:

   • Sau khi tính toán hết các mask, dp[(1 << n) - 1] sẽ chứa chi phí nhỏ nhất để ghép cặp tất cả N phần tử.

Ví dụ 2: Ghép cặp song phương (Bipartite Matching) với giá trị lớn nhất

Bài toán: Bạn có N người nam và N người nữ. Bạn biết "điểm tương hợp" score[i][j] khi người nam thứ i ghép cặp với người nữ thứ j. Tìm cách ghép cặp mỗi người nam với một người nữ duy nhất (và ngược lại) sao cho tổng điểm tương hợp là lớn nhất.

Input: Số nguyên N (<= 20) và ma trận điểm score[i][j] kích thước N x N.

Output: Tổng điểm tương hợp lớn nhất.

Phân tích:

• Đây là bài toán Ghép cặp hoàn hảo có trọng số trên đồ thị hai phía (Bipartite Graph).
• Thay vì ghép cặp các phần tử trong cùng một tập, chúng ta ghép cặp các phần tử từ hai tập khác nhau (nam và nữ).
• Sử dụng DP Bitmask: dp[mask] sẽ là giá trị lớn nhất đạt được khi đã ghép cặp k người nam đầu tiên (với k là số bit 1 trong mask) với tập hợp con những người nữ được biểu diễn bởi mask.

Công thức DP Bitmask cho bài toán cực đại hóa giá trị trên đồ thị hai phía:

dp[mask] = giá trị lớn nhất khi đã ghép cặp k người nam đầu tiên (0, 1, ..., k-1) với tập hợp k người nữ được biểu diễn bởi mask. Ở đây k là số bit 1 trong mask (__builtin_popcount(mask)).

Chuyển trạng thái: Để tính dp[mask] (tức là đã ghép cặp k người nam đầu tiên với tập nữ mask), người nam thứ k-1 bắt buộc phải được ghép với một người nữ j nào đó trong tập nữ mask.

dp[mask] = max(dp[mask ^ (1 << j)] + score[k-1][j])

với:

• k = __builtin_popcount(mask) (số lượng nam đã ghép = số lượng nữ đã ghép).
• j là chỉ số bất kỳ sao cho bit thứ j của mask là 1 (người nữ j có trong tập con).
• score[k-1][j] là điểm tương hợp khi ghép nam k-1 với nữ j.

Trường hợp cơ sở: dp[0] = 0 (0 nam ghép với 0 nữ, giá trị 0).

Kết quả cuối cùng: dp[(1 << N) - 1] (mask có tất cả N bit là 1, biểu diễn việc đã ghép cặp tất cả N người nam với tất cả N người nữ).

Mã C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int NEGINF = numeric_limits<int>::min(); // Dùng cho bài toán cực đại hóa

int score[20][20]; // Ma trận điểm tương hợp, N <= 20
int dp[1 << 20]; // dp[mask]

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Đọc ma trận điểm
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> score[i][j];
        }
    }

    // Khởi tạo DP
    // dp[mask] = NEGINF cho tất cả các mask trừ dp[0]
    for (int i = 0; i < (1 << n); ++i) {
        dp[i] = NEGINF;
    }
    dp[0] = 0; // Trạng thái không có cặp nào được tạo ra có giá trị 0

    // Tính toán DP
    // Duyệt qua tất cả các mask từ 0 đến 2^n - 1
    for (int mask = 0; mask < (1 << n); ++mask) {
        // Nếu dp[mask] vẫn là NEGINF, nghĩa là trạng thái này không thể đạt được
        if (dp[mask] == NEGINF) {
            continue;
        }

        // Số lượng nam đã được ghép cặp bằng số lượng nữ trong mask
        int k = __builtin_popcount(mask);

        // Nếu đã ghép đủ N nam, bỏ qua
        if (k == n) {
            continue;
        }

        // Chúng ta đang ghép cặp người nam thứ k (chỉ số 0-indexed)
        int current_man = k;

        // Người nam thứ k sẽ ghép với một người nữ j CHƯA được ghép (bit thứ j trong mask là 0)
        for (int j = 0; j < n; ++j) {
            // Nếu người nữ j CHƯA có trong mask (bit j là 0)
            if (!((mask >> j) & 1)) {
                // Mask mới sau khi ghép nam k với nữ j: thêm nữ j vào mask
                int next_mask = mask | (1 << j);

                // Cập nhật trạng thái dp[next_mask]
                // dp[next_mask] có thể đạt tới bằng cách ghép (nam k, nữ j) từ trạng thái mask
                dp[next_mask] = max(dp[next_mask], dp[mask] + score[current_man][j]);
            }
        }
    }

    // Kết quả là dp của mask có tất cả các bit là 1
    cout << dp[(1 << n) - 1] << endl;

    return 0;
}

Giải thích mã:

1. Includes và Khởi tạo: Tương tự ví dụ 1, nhưng NEGINF cho bài toán cực đại.

2. Vòng lặp DP:

   • Lặp qua tất cả các mask. mask ở đây biểu diễn tập hợp các người nữ đã được ghép cặp.
   • dp[mask] == NEGINF kiểm tra xem trạng thái hiện tại có hợp lệ không.
   • int k = __builtin_popcount(mask); tính số lượng bit 1 trong mask, cho biết đã có k người nữ được sử dụng. Điều này cũng có nghĩa là chúng ta đã ghép cặp được k người nam đầu tiên (nam 0 đến nam k-1).
   • Nếu k == n, nghĩa là tất cả N người nam đã được ghép (với N người nữ trong mask), chúng ta đã đạt trạng thái cuối hoặc trạng thái trung gian của lời giải cuối cùng. Bỏ qua.
   • current_man = k: Người nam tiếp theo cần được ghép là người có chỉ số k.
   • Lặp qua tất cả người nữ j từ 0 đến n-1.
   • if (!((mask >> j) & 1)): Kiểm tra xem người nữ j đã được sử dụng trong các cặp trước đó hay chưa. Nếu chưa (bit j của mask là 0).
   • next_mask = mask | (1 << j): Mask mới biểu diễn tập hợp nữ sau khi thêm nữ j.
   • dp[next_mask] = max(dp[next_mask], dp[mask] + score[current_man][j]);: Công thức chuyển trạng thái. Giá trị lớn nhất khi ghép k nam với tập nữ next_mask có thể đạt được bằng cách lấy giá trị lớn nhất khi ghép k-1 nam với tập nữ mask (bỏ đi nữ j) rồi cộng thêm điểm score[current_man][j].

3. Kết quả:

   • dp[(1 << n) - 1] chứa giá trị lớn nhất khi đã ghép cặp tất cả N người nam với N người nữ.

Lưu ý quan trọng về DP Bitmask

• Kích thước N: DP Bitmask hiệu quả nhất khi N nhỏ (thường dưới 20-25), do độ phức tạp O(N * 2^N).
• Định nghĩa trạng thái: Việc định nghĩa dp[mask] và tìm công thức chuyển trạng thái là bước quan trọng nhất. Nó phụ thuộc vào cấu trúc cụ thể của bài toán. Hãy luôn tự hỏi: Trạng thái mask biểu diễn điều gì? và Làm sao để xây dựng trạng thái mask từ các trạng thái nhỏ hơn?
• Thứ tự tính toán: Duyệt mask tăng dần từ 0 đến 2^N - 1 thường đảm bảo các trạng thái nhỏ hơn được tính trước khi chúng được sử dụng để tính các trạng thái lớn hơn.
• Tối ưu hóa bitwise: Sử dụng các phép toán bitwise (&, |, ^, ~, <<, >>) và các hàm built-in của compiler như __builtin_popcount, __builtin_ctz có thể giúp code ngắn gọn và hiệu quả hơn.

Bài tập ví dụ:

Trò chơi số nguyên tố

Trong một buổi thử nghiệm ứng dụng di động mới, FullHouse Dev đã tạo ra một trò chơi thú vị trên điện thoại thông minh. Trò chơi này có tên là "Trò chơi số nguyên tố", nơi hai người chơi Alice và Bob sẽ thay phiên nhau xóa các chữ số từ một số nguyên cho đến khi một người thua cuộc.

Bài toán

Cho một số nguyên \(N\) chỉ bao gồm các chữ số 2, 3, 5, 7. Alice và Bob chơi theo luật sau:

• Alice là người bắt đầu, sau đó hai người lần lượt thay phiên nhau.
• Trong mỗi lượt, người chơi phải xóa một chữ số ở đầu hoặc cuối của số nguyên \(N\).
• Người chơi nào làm cho số còn lại trở thành số nguyên tố sẽ thua cuộc.
• Lưu ý rằng khi số chỉ còn một chữ số, nó luôn là số nguyên tố vì chỉ có thể là 2, 3, 5 hoặc 7.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\)

OUTPUT FORMAT:

• Với mỗi test case, in ra một dòng:
  • In "Alice" nếu Alice thắng
  • In "Bob" nếu Bob thắng (giả định cả hai người chơi đều chơi tối ưu)

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(N\) chỉ chứa các chữ số 2, 3, 5, 7
• \(N\) không phải là số nguyên tố
• Test set 1 (35 điểm): \(N\) có độ dài \(\leq 4\)
• Test set 2 (50 điểm): \(N\) có độ dài \(\leq 8\)
• Test set 3 (15 điểm): \(N\) có độ dài \(\leq 18\)

Ví dụ

INPUT

2
3237
3273

OUTPUT

Alice
Bob

Giải thích

Ở test case đầu tiên với số 3237:

• Alice có thể chọn xóa số ở đầu hoặc cuối để được 237 hoặc 323.
• Nếu Alice chọn 323: Bob có thể chọn 32 (vì nếu chọn 23 là số nguyên tố sẽ thua ngay). Sau đó Alice buộc phải chọn một trong hai số 3 hoặc 2, đều là số nguyên tố nên sẽ thua.
• Tuy nhiên, nếu Alice chọn xóa số 3 ở đầu để được 237: Bob sẽ thua vì dù chọn cách nào cũng sẽ được số nguyên tố Đây là một bài toán trò chơi hai người chơi với thông tin đầy đủ, không có yếu tố ngẫu nhiên và kết thúc trong số bước hữu hạn. Đây là dạng bài toán điển hình có thể giải bằng phương pháp Quy hoạch động (Dynamic Programming) hoặc phân tích trạng thái Thắng/Thua (Winning/Losing positions).

Hướng giải ngắn gọn:

1. Xác định trạng thái: Trạng thái của trò chơi tại một thời điểm được xác định bởi đoạn con (substring) của số nguyên \(N\) còn lại. Ta có thể biểu diễn một trạng thái bằng cặp chỉ số (i, j) là chỉ số bắt đầu và kết thúc của đoạn con trong số nguyên \(N\) ban đầu.

2. Định nghĩa DP: Gọi dp[i][j] là một giá trị boolean cho biết người chơi đến lượt tại trạng thái (i, j) (với đoạn con N[i...j]) có thể thắng hay không, giả sử cả hai chơi tối ưu.

3. Trường hợp cơ sở:

   • Xét các đoạn con có độ dài bằng 1 (len = 1, tức i = j). Số còn lại chỉ là một chữ số (2, 3, 5, hoặc 7), đây luôn là số nguyên tố. Theo luật, người chơi nào làm cho số còn lại là số nguyên tố sẽ thua. Điều này có nghĩa là người chơi trước đó đã thực hiện nước đi dẫn đến trạng thái một chữ số (prime). Do đó, người chơi hiện tại (đến lượt tại trạng thái một chữ số) sẽ là người thắng cuộc (vì người trước đó đã thua).
   • Vậy, dp[i][i] = true cho mọi i (vì số có 1 chữ số luôn nguyên tố, người chơi đối diện với số nguyên tố sẽ thắng).

4. Công thức chuyển trạng thái:

   • Xét đoạn con N[i...j] có độ dài len > 1.
   • Chuyển đoạn con này thành một số nguyên val.
   • Kiểm tra xem val có phải là số nguyên tố không.
   • Nếu val là số nguyên tố: Người chơi đến lượt tại trạng thái này là người thua (vì người trước đó đã làm cho nó không nguyên tố, và giờ người này bị buộc phải đối mặt với một số nguyên tố nếu không có cách khác). Tuy nhiên, định nghĩa DP là người chơi hiện tại có thắng không. Nếu số N[i...j] là nguyên tố, thì người chơi trước đó đã tạo ra số nguyên tố này, và họ đã thua. Người chơi hiện tại (đến lượt ở trạng thái nguyên tố) sẽ thắng. Vậy, nếu val là số nguyên tố, dp[i][j] = true.
   • Nếu val không phải là số nguyên tố: Người chơi hiện tại có hai lựa chọn:
     • Xóa chữ số đầu: Dẫn đến trạng thái (i+1, j) (đoạn con N[i+1...j]).
     • Xóa chữ số cuối: Dẫn đến trạng thái (i, j-1) (đoạn con N[i...j-1]).
     • Người chơi hiện tại thắng nếu có ít nhất một nước đi dẫn đến một trạng thái mà người chơi kế tiếp (đối thủ) sẽ thua.
     • Người chơi kế tiếp tại trạng thái (i+1, j) thua nếu dp[i+1][j] là false.
     • Người chơi kế tiếp tại trạng thái (i, j-1) thua nếu dp[i][j-1] là false.
     • Vậy, nếu val không nguyên tố: dp[i][j] = (!dp[i+1][j]) || (!dp[i][j-1]). (Người chơi hiện tại thắng nếu đối thủ thua khi nhận trạng thái tiếp theo từ nước đi đầu tiên HOẶC đối thủ thua khi nhận trạng thái tiếp theo từ nước đi thứ hai). Lưu ý chỉ xét các nước đi hợp lệ (len > 1).

5. Thứ tự tính DP: Ta cần tính các trạng thái của đoạn con ngắn trước rồi mới tính các trạng thái của đoạn con dài hơn. Ta có thể lặp theo độ dài của đoạn con len từ 1 đến độ dài ban đầu của \(N\). Với mỗi độ dài len, ta lặp qua các chỉ số bắt đầu i tương ứng, và chỉ số kết thúc j sẽ là i + len - 1.

6. Kiểm tra số nguyên tố: Vì số có thể có độ dài lên đến 18 chữ số, giá trị của nó có thể rất lớn (lên tới khoảng 10^18). Việc kiểm tra nguyên tố cho các số lớn này cần thuật toán hiệu quả hơn phép chia thử thông thường đến căn bậc hai. Thuật toán Miller-Rabin là một lựa chọn phù hợp cho trường hợp này (kết hợp với kiểm tra nhanh các số nhỏ bằng phép chia thử).

7. Kết quả: Trạng thái ban đầu là toàn bộ số \(N\), tức trạng thái (0, L-1) với L là độ dài của \(N\). Alice là người đi đầu. Nếu dp[0][L-1] là true, Alice thắng. Nếu dp[0][L-1] là false, Bob thắng.

Tóm tắt DP:

dp[i][j] = true nếu số N[i...j] là nguyên tố dp[i][j] = !dp[i+1][j] || !dp[i][j-1] nếu số N[i...j] không nguyên tố (và len > 1)

Lưu ý rằng số N ban đầu được đảm bảo không phải số nguyên tố, nên trường hợp dp[0][L-1] = true do N[0...L-1] là nguyên tố sẽ không xảy ra.

Cần cài đặt các hàm hỗ trợ:

• Chuyển đổi chuỗi con sang số nguyên (dùng unsigned long long hoặc long long).
• Hàm kiểm tra số nguyên tố hiệu quả cho số lớn.

Cấu trúc lặp DP:

// L = do dai cua N
bool dp[L][L];

for (int len = 1; len <= L; ++len) {
    for (int i = 0; i <= L - len; ++i) {
        int j = i + len - 1;
        // Trich xuat doan con N[i...j], chuyen sang so ull val
        unsigned long long val = stringToUll(N.substr(i, len));

        bool is_prime = isPrime(val);

        if (is_prime) {
            dp[i][j] = true; // Nguoi choi den luot tai trang thai nay thang
        } else {
            bool can_win = false;
            if (len > 1) {
                // Xoa dau: chuyen sang (i+1, j). Thang neu doi thu thua tai do (!dp[i+1][j])
                if (!dp[i+1][j]) can_win = true;
                // Xoa cuoi: chuyen sang (i, j-1). Thang neu doi thu thua tai do (!dp[i][j-1])
                if (!dp[i][j-1]) can_win = true;
            }
            dp[i][j] = can_win;
        }
    }
}

// Ket qua: Alice thang neu dp[0][L-1] la true
if (dp[0][L-1]) {
    cout << "Alice";
} else {
    cout << "Bob";
}

Lưu ý kiểm tra len > 1 khi truy cập dp[i+1][j] và dp[i][j-1].

Làm thêm nhiều bài tập miễn phí tại đây