Khóa học CTDL và GT

Bài 28.5. Bài tập cơ bản về DP Bitmask

Trong thế giới của các thuật toán và lập trình cạnh tranh, có những bài toán mà bạn cần xem xét tất cả các tập con của một tập hợp hoặc tất cả các hoán vị của một tập hợp. Khi kích thước của tập hợp (gọi là N) đủ nhỏ (thường là N <= 20), chúng ta có một kỹ thuật mạnh mẽ để đối phó với chúng: Quy hoạch động kết hợp Bitmask (DP Bitmask).

Bài viết này sẽ đi sâu vào những khái niệm cơ bản nhất của DP Bitmask thông qua các ví dụ minh họa chi tiết bằng C++.

Bitmask là gì và tại sao lại dùng nó trong DP?

Bitmask đơn giản là việc sử dụng một số nguyên để biểu diễn một tập hợp con. Mỗi bit trong số nguyên đó tương ứng với một phần tử của tập hợp ban đầu. Nếu bit thứ i được đặt (bằng 1), điều đó có nghĩa là phần tử thứ i nằm trong tập con đang xét. Nếu bit thứ i không được đặt (bằng 0), phần tử thứ i không nằm trong tập con đó.

Ví dụ, với N = 4 phần tử, chúng ta có thể biểu diễn các tập con như sau:

• 0000 (binary) = 0 (decimal): Tập rỗng {}.
• 0001 = 1: Tập {phần tử 0}.
• 0010 = 2: Tập {phần tử 1}.
• 0011 = 3: Tập {phần tử 0, phần tử 1}.
• 1111 = 15: Tập {phần tử 0, phần tử 1, phần tử 2, phần tử 3}.

Một số nguyên 32-bit có thể biểu diễn tập con của tập có tối đa 32 phần tử. Với N <= 20, chúng ta có thể dễ dàng sử dụng kiểu dữ liệu int hoặc long long.

Tại sao kết hợp Bitmask với DP?

Trong nhiều bài toán quy hoạch động, trạng thái (state) của DP cần lưu trữ thông tin về việc những phần tử nào đã được xử lý, đã được chọn, hoặc đã được thăm dò. Bitmask cung cấp một cách nhỏ gọn và hiệu quả để biểu diễn chính xác thông tin này. Thay vì phải lưu trữ một mảng boolean hoặc một danh sách các phần tử đã chọn (có thể thay đổi kích thước), chúng ta chỉ cần một số nguyên duy nhất.

Trạng thái DP thường có dạng dp[mask], trong đó mask là một số nguyên biểu diễn tập hợp các phần tử đã được xử lý để đạt được trạng thái đó. Số lượng trạng thái là 2^N, vì có 2^N tập con của tập N phần tử. Điều này giải thích tại sao kỹ thuật này chỉ hiệu quả khi N nhỏ.

Các phép toán bitwise (&, |, ^, <<, >>, ~) trở thành công cụ mạnh mẽ để thao tác với các tập con:

• mask & (1 << i): Kiểm tra xem phần tử i có trong tập mask không.
• mask | (1 << i): Thêm phần tử i vào tập mask.
• mask ^ (1 << i): Loại bỏ phần tử i khỏi tập mask (nếu nó tồn tại) hoặc thêm vào (nếu chưa tồn tại - cẩn thận khi sử dụng). Thường dùng khi biết chắc phần tử i có hoặc không có trong mask.
• mask & ~(1 << i): Loại bỏ phần tử i khỏi tập mask.

Cấu trúc chung của DP Bitmask

Thông thường, một bài toán DP Bitmask sẽ có cấu trúc như sau:

1. Xác định trạng thái DP: dp[mask] thường là giá trị tối ưu (min/max cost, count, ...) cho tập con được biểu diễn bởi mask. Đôi khi cần thêm thông tin, ví dụ dp[mask][last_element] (như trong TSP).
2. Khởi tạo: Gán giá trị ban đầu cho dp table (0 cho đếm/tổng, INF cho min, -INF cho max). Thiết lập trạng thái cơ sở (base case), thường là dp[0] (tập rỗng).
3. Chuyển trạng thái: Lặp qua các mask từ 0 đến 2^N - 1. Với mỗi mask, xem xét thêm một phần tử mới i chưa có trong mask để tạo thành mask | (1 << i). Cập nhật dp[mask | (1 << i)] dựa trên dp[mask] và chi phí/lợi ích khi thêm phần tử i. Hoặc đôi khi lặp qua các mask và xem xét phần tử cuối cùng được thêm vào để đạt được mask đó.
4. Kết quả: Kết quả cuối cùng thường nằm ở dp[(1 << N) - 1] (tập hợp tất cả N phần tử) hoặc một trạng thái mask nào đó đặc thù của bài toán.

Bây giờ, chúng ta sẽ đi vào các ví dụ cụ thể để làm rõ hơn.

Ví dụ 1: Phân công công việc (Assignment Problem - Dạng đơn giản)

Bài toán: Cho N công nhân và N công việc. Chi phí để công nhân i thực hiện công việc j là cost[i][j]. Tìm cách phân công mỗi công nhân một công việc sao cho tổng chi phí là nhỏ nhất. N <= 15.

Đây là một bài toán kinh điển có thể giải bằng luồng hoặc thuật toán Kuhn-Munkres (Hungarian algorithm), nhưng với N nhỏ, DP Bitmask là một cách tiếp cận hiệu quả và dễ hiểu hơn cho trường hợp này.

Phân tích:

• Chúng ta cần đảm bảo mỗi công nhân được giao một công việc và mỗi công việc được giao cho một công nhân.
• Khi xem xét việc giao công việc cho công nhân thứ k, chúng ta cần biết những công việc nào đã được giao cho k-1 công nhân trước đó để tránh giao lại.
• Thông tin về "những công việc nào đã được giao" là thứ có thể biểu diễn bằng bitmask.

Định nghĩa trạng thái DP:

• dp[mask] = Chi phí nhỏ nhất để phân công các công việc được biểu diễn bởi mask cho các công nhân đầu tiên.
• Số lượng công nhân đã được sử dụng để hoàn thành các công việc trong mask chính là số lượng bit 1 trong mask. Nếu mask có k bit 1, thì dp[mask] là chi phí nhỏ nhất để k công nhân đầu tiên (theo thứ tự 0, 1, ..., k-1) hoàn thành k công việc tương ứng với các bit 1 trong mask.

Trạng thái cơ sở:

• dp[0] = 0: Tập công việc rỗng được hoàn thành bởi 0 công nhân với chi phí 0.
• Tất cả các trạng thái dp[mask] khác ban đầu được gán bằng một giá trị rất lớn (vô cùng) để đảm bảo phép min hoạt động đúng.

Chuyển trạng thái: Chúng ta sẽ xây dựng các trạng thái mask theo thứ tự tăng dần số lượng bit 1. Giả sử chúng ta đang tính dp[mask]. mask có k bit 1, tức là k công việc đã được phân công cho k công nhân đầu tiên (công nhân 0 đến k-1). Công nhân tiếp theo là công nhân thứ k. Công nhân k này sẽ nhận một công việc j mà chưa được phân công trước đó (bit thứ j trong mask bằng 0). Để tính dp[mask], công nhân cuối cùng được sử dụng là công nhân có chỉ số k-1 (nếu mask có k bit 1). Công nhân này được phân công một công việc j nào đó trong tập mask. Trạng thái trước đó sẽ là mask bỏ đi công việc j, tức là mask ^ (1 << j). Trạng thái mask ^ (1 << j) có k-1 bit 1, và nó biểu diễn việc k-1 công nhân đầu tiên đã hoàn thành các công việc trong tập mask ^ (1 << j). Công nhân thứ k-1 (chỉ số k-1) được phân công công việc j. Vì vậy, công thức chuyển trạng thái là: dp[mask] = min(dp[mask ^ (1 << j)] + cost[k-1][j]) với mọi công việc j mà bit thứ j được đặt trong mask, và k là số lượng bit 1 trong mask.

Cách lặp hiệu quả hơn: Lặp qua tất cả các mask từ 0 đến (1 << N) - 1. Đối với mỗi mask, xác định số lượng công nhân đã được sử dụng là k = __builtin_popcount(mask) (hàm đếm bit 1 trong GCC/Clang). Công nhân tiếp theo cần được phân công là công nhân thứ k. Duyệt qua tất cả các công việc j từ 0 đến N-1. Nếu công việc j chưa được phân công trong mask (tức là bit thứ j trong mask bằng 0), ta có thể phân công công việc j cho công nhân thứ k. Trạng thái mới sẽ là mask | (1 << j). Cập nhật: dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[k][j])

Kết quả: Kết quả cuối cùng là dp[(1 << N) - 1], là chi phí nhỏ nhất để phân công tất cả N công việc cho N công nhân đầu tiên.

Mã C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // For std::pow (optional, can use bit shift)
#include <limits> // For std::numeric_limits

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

int main() {
    int N;
    std::cin >> N;

    // cost[i][j]: chi phí công nhân i làm công việc j
    std::vector<std::vector<int>> cost(N, std::vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            std::cin >> cost[i][j];
        }
    }

    // dp[mask]: chi phí nhỏ nhất để các công việc trong mask được hoàn thành
    // bởi số lượng công nhân = số bit 1 trong mask
    std::vector<int> dp(1 << N, INF);

    // Trạng thái cơ sở: không có công việc nào được hoàn thành, chi phí 0
    dp[0] = 0;

    // Lặp 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] là vô cùng, trạng thái này không thể đạt được, bỏ qua
        if (dp[mask] == INF) {
            continue;
        }

        // Số lượng công việc đã được hoàn thành trong mask (cũng là chỉ số của công nhân tiếp theo)
        int workers_assigned = 0;
        // Sử dụng hàm __builtin_popcount để đếm số bit 1 nhanh chóng
        // Hoặc có thể tự đếm bằng vòng lặp hoặc hàm bitcount thủ công
        #ifdef __GNUC__
        workers_assigned = __builtin_popcount(mask);
        #else
        // Manual bit count if not using GCC/Clang
        int temp_mask = mask;
        while(temp_mask > 0){
            if(temp_mask & 1) workers_assigned++;
            temp_mask >>= 1;
        }
        #endif


        // Nếu đã phân công đủ N công nhân, không cần làm gì nữa
        if (workers_assigned == N) {
            continue;
        }

        // Công nhân tiếp theo cần phân công là công nhân có chỉ số 'workers_assigned'
        int current_worker = workers_assigned;

        // Duyệt qua tất cả N công việc
        for (int job = 0; job < N; ++job) {
            // Kiểm tra xem công việc 'job' đã được phân công trong mask hiện tại chưa
            // Nếu bit thứ 'job' của mask là 0, tức là công việc 'job' chưa được phân công
            if (!(mask & (1 << job))) {
                // Nếu công việc 'job' chưa được phân công, ta có thể phân công nó cho 'current_worker'
                // Tạo mask mới bằng cách thêm công việc 'job' vào mask hiện tại
                int next_mask = mask | (1 << job);

                // Cập nhật chi phí nhỏ nhất để đạt được next_mask
                // Chi phí mới = chi phí để đạt mask hiện tại + chi phí 'current_worker' làm 'job'
                dp[next_mask] = std::min(dp[next_mask], dp[mask] + cost[current_worker][job]);
            }
        }
    }

    // Kết quả là chi phí nhỏ nhất để hoàn thành tất cả N công việc (mask có tất cả bit 1)
    std::cout << "Minimum cost: " << dp[(1 << N) - 1] << std::endl;

    return 0;
}

Giải thích mã:

1. Include và Khởi tạo: Bao gồm các thư viện cần thiết. INF được định nghĩa là giá trị lớn nhất của int để biểu diễn vô cùng. Đọc vào N và ma trận cost.
2. Mảng DP: dp là một vector có kích thước 1 << N (tức 2^N), đại diện cho tất cả 2^N trạng thái mask có thể có. Khởi tạo tất cả giá trị bằng INF, trừ dp[0] bằng 0.
3. Vòng lặp Mask: Duyệt qua tất cả các mask từ 0 đến (1 << N) - 1. Vòng lặp này đảm bảo rằng khi ta tính dp[next_mask], giá trị dp[mask] (với mask có ít bit 1 hơn) đã được tính xong.
4. Kiểm tra Trạng thái Không Đạt Được: if (dp[mask] == INF) continue; bỏ qua các mask mà ta không thể đạt tới (chi phí vẫn là vô cùng).
5. Xác định Công nhân Hiện tại: workers_assigned đếm số lượng bit 1 trong mask. Đây là số công việc đã được phân công, và cũng là chỉ số của công nhân tiếp theo sẽ được xem xét (do ta gán công nhân 0, 1, 2,... theo thứ tự). __builtin_popcount(mask) là một hàm dựng sẵn (built-in) trong GCC/Clang giúp đếm số bit 1 rất nhanh.
6. Vòng lặp Công việc: Duyệt qua tất cả các công việc job từ 0 đến N-1.
7. Kiểm tra Công việc Chưa Được Giao: if (!(mask & (1 << job))) kiểm tra xem bit thứ job có phải là 0 trong mask hay không. Nếu đúng, công việc job chưa được phân công.
8. Chuyển trạng thái: Nếu công việc job chưa được giao, ta thử giao nó cho current_worker. Mask mới next_mask sẽ là mask với bit thứ job được đặt lên 1 (mask | (1 << job)). Chi phí để đạt next_mask thông qua việc phân công công việc job cho current_worker là dp[mask] + cost[current_worker][job]. Ta cập nhật dp[next_mask] bằng giá trị nhỏ nhất giữa giá trị hiện tại của nó và chi phí mới tính được.
9. Kết quả: Sau khi vòng lặp kết thúc, dp[(1 << N) - 1] sẽ chứa chi phí nhỏ nhất để hoàn thành tất cả N công việc.

Lưu ý: Trong ví dụ này, ta giả định rằng công nhân 0 thực hiện một trong các công việc đầu tiên được thêm vào mask, công nhân 1 thực hiện công việc tiếp theo, v.v. Điều này hoạt động vì bài toán yêu cầu một cách phân công bất kỳ mỗi công nhân một công việc. Việc gán "công nhân thứ k làm công việc mới được thêm vào" là một cách suy luận để đảm bảo mỗi công nhân (theo chỉ số 0 đến N-1) đều được xem xét cho một công việc duy nhất. Số bit 1 trong mask tự nhiên tăng từ 0 đến N, đảm bảo mỗi công nhân theo chỉ số được sử dụng đúng một lần khi mask đạt kích thước tương ứng.

Ví dụ 2: Bài toán Người Du Lịch (Traveling Salesperson Problem - TSP) - Dạng đơn giản nhất

Bài toán: Cho N thành phố và ma trận khoảng cách dist[i][j] giữa thành phố i và thành phố j. Tìm đường đi ngắn nhất bắt đầu từ thành phố 0, thăm mỗi thành phố đúng một lần và quay trở lại thành phố 0. N <= 15.

Đây là bài toán TSP kinh điển, NP-Hard nói chung, nhưng với N nhỏ có thể giải bằng DP Bitmask.

Phân tích:

• Ta cần thăm tất cả các thành phố.
• Thứ tự thăm các thành phố quan trọng.
• Khi ở một thành phố, ta cần biết mình đã đi qua những thành phố nào để không thăm lại (trừ thành phố bắt đầu ở cuối hành trình).

Định nghĩa trạng thái DP:

• Ở đây, chỉ dùng dp[mask] không đủ. Ta cần biết mình đang ở thành phố nào sau khi đã thăm các thành phố trong mask.
• dp[mask][last_city] = Chiều dài đường đi ngắn nhất thăm tất cả các thành phố được biểu diễn bởi mask, và kết thúc tại last_city.
• mask: Bitmask biểu diễn tập hợp các thành phố đã thăm.
• last_city: Chỉ số của thành phố cuối cùng trong đường đi hiện tại. last_city phải là một bit được đặt trong mask.

Trạng thái cơ sở:

• Ta bắt đầu từ thành phố 0. Trạng thái ban đầu chỉ thăm thành phố 0, kết thúc tại thành phố 0.
• dp[1][0] = 0: Mask 1 (binary 00...01) biểu diễn chỉ thăm thành phố 0. Kết thúc tại thành phố 0. Chi phí là 0.
• Tất cả các trạng thái dp[mask][last_city] khác ban đầu được gán bằng INF.

Chuyển trạng thái: Chúng ta sẽ lặp qua các mask theo thứ tự tăng dần số lượng thành phố đã thăm. Đối với mỗi mask (từ 1 đến (1 << N) - 1): Đối với mỗi thành phố u từ 0 đến N-1: Nếu thành phố u nằm trong mask (tức bit thứ u trong mask được đặt): Và nếu dp[mask][u] có thể đạt được (khác INF): Ta đang ở trạng thái đã thăm các thành phố trong mask và đang dừng ở thành phố u. Ta xem xét đi đến một thành phố v chưa được thăm (tức bit thứ v trong mask bằng 0). Trạng thái mới sẽ là đã thăm các thành phố trong mask | (1 << v) và kết thúc tại thành phố v. Cập nhật: dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v])

Kết quả: Sau khi tính toán tất cả các trạng thái dp[mask][last_city], trạng thái cuối cùng ta quan tâm là đã thăm tất cả các thành phố (mask (1 << N) - 1). Từ mỗi thành phố i (i != 0) trong tập này, ta cần tính thêm chi phí để quay trở lại thành phố 0. Kết quả cuối cùng là min(dp[(1 << N) - 1][i] + dist[i][0]) với mọi thành phố i từ 1 đến N-1 (vì ta đã bắt đầu từ 0, nên thành phố cuối cùng trước khi về 0 không thể là 0).

Mã C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits> // For std::numeric_limits

const int INF = std::numeric_limits<int>::max() / 2; // Use a smaller INF to prevent overflow during addition

int main() {
    int N;
    std::cin >> N;

    // dist[i][j]: khoảng cách từ thành phố i đến thành phố j
    std::vector<std::vector<int>> dist(N, std::vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            std::cin >> dist[i][j];
        }
    }

    // dp[mask][last_city]: độ dài đường đi ngắn nhất thăm các thành phố trong mask, kết thúc tại last_city
    std::vector<std::vector<int>> dp(1 << N, std::vector<int>(N, INF));

    // Trạng thái cơ sở: chỉ thăm thành phố 0, kết thúc tại thành phố 0, chi phí 0
    // Mask 1 (0...01) biểu diễn chỉ thăm thành phố 0
    dp[1][0] = 0;

    // Lặp qua tất cả các mask từ 1 (chỉ thăm thành phố 0) đến 2^N - 1 (thăm tất cả thành phố)
    for (int mask = 1; mask < (1 << N); ++mask) {
        // Lặp qua tất cả các thành phố u có thể là thành phố cuối cùng trong mask hiện tại
        for (int u = 0; u < N; ++u) {
            // Nếu thành phố u nằm trong mask và trạng thái dp[mask][u] có thể đạt được
            if ((mask & (1 << u)) && dp[mask][u] != INF) {
                // Xét đi từ thành phố u đến một thành phố v chưa được thăm
                for (int v = 0; v < N; ++v) {
                    // Nếu thành phố v chưa được thăm trong mask (bit v bằng 0)
                    if (!(mask & (1 << v))) {
                        // Tạo mask mới: thêm thành phố v vào mask hiện tại
                        int next_mask = mask | (1 << v);

                        // Cập nhật dp[next_mask][v]
                        // Chi phí mới = chi phí đến mask hiện tại kết thúc tại u + khoảng cách từ u đến v
                        dp[next_mask][v] = std::min(dp[next_mask][v], dp[mask][u] + dist[u][v]);
                    }
                }
            }
        }
    }

    // Tính kết quả cuối cùng: quay trở lại thành phố 0 từ tất cả các thành phố có thể là điểm cuối
    // sau khi đã thăm tất cả N thành phố (mask = (1 << N) - 1)
    int min_cost = INF;
    int final_mask = (1 << N) - 1; // Mask biểu diễn đã thăm tất cả các thành phố

    // Lặp qua tất cả các thành phố i (khác thành phố 0 ban đầu)
    // i có thể là thành phố cuối cùng trước khi quay về 0
    for (int i = 1; i < N; ++i) {
        // Nếu trạng thái đã thăm tất cả các thành phố và kết thúc tại i có thể đạt được
        if (dp[final_mask][i] != INF) {
            // Tính tổng chi phí: chi phí đến i + khoảng cách từ i về 0
            min_cost = std::min(min_cost, dp[final_mask][i] + dist[i][0]);
        }
    }

    std::cout << "Minimum TSP cost: " << min_cost << std::endl;

    return 0;
}

Giải thích mã:

1. Include và Khởi tạo: Bao gồm thư viện. INF được chọn cẩn thận để tránh tràn số khi cộng khoảng cách. Đọc vào N và ma trận dist.
2. Mảng DP: dp là một vector 2D có kích thước (1 << N) x N. dp[mask][last_city] lưu trữ chi phí. Khởi tạo tất cả bằng INF, trừ dp[1][0] bằng 0. Mask 1 chỉ có bit 0 được đặt, biểu diễn tập {thành phố 0}.
3. Vòng lặp Mask: Lặp từ mask 1 đến (1 << N) - 1.
4. Vòng lặp Thành phố Cuối u: Lặp qua tất cả các thành phố u. Chỉ xử lý nếu u nằm trong mask và dp[mask][u] khác INF.
5. Vòng lặp Thành phố Tiếp Theo v: Lặp qua tất cả các thành phố v. Chỉ xử lý nếu v chưa nằm trong mask.
6. Chuyển trạng thái: Ta có thể đi từ u đến v. Mask mới next_mask có thêm thành phố v. Cập nhật dp[next_mask][v] bằng min so với chi phí hiện tại cộng với dist[u][v].
7. Kết quả Cuối cùng: Sau khi tính toán xong DP, ta đã có chi phí nhỏ nhất để thăm tất cả các thành phố kết thúc tại một thành phố i bất kỳ (dp[(1 << N) - 1][i]). Để hoàn thành tour, ta cần đi từ thành phố i đó về lại thành phố 0. Vòng lặp cuối cùng tìm giá trị nhỏ nhất của dp[(1 << N) - 1][i] + dist[i][0] cho tất cả i từ 1 đến N-1 (vì tour bắt đầu ở 0, nên điểm cuối cùng trước khi về 0 không thể là 0).

Những điểm cần lưu ý khi sử dụng DP Bitmask

• Kích thước N: Đây là yếu tố hạn chế lớn nhất. DP Bitmask chỉ khả thi khi N <= 20 (hoặc khoảng 25-26 với long long và các kỹ thuật tối ưu nhỏ), vì số trạng thái tăng theo cấp số nhân 2^N.
• Định nghĩa trạng thái: Cần định nghĩa chính xác dp[mask] hoặc dp[mask][...] đại diện cho điều gì. Điều này quyết định cách bạn xây dựng chuyển trạng thái và base case.
• Base Case: Xác định rõ trạng thái khởi đầu với chi phí/giá trị đã biết.
• Thứ tự lặp: Trong hầu hết các trường hợp, bạn cần lặp qua các mask theo thứ tự tăng dần (từ 0 đến 2^N - 1) hoặc theo số lượng bit 1 tăng dần, để đảm bảo khi tính một trạng thái mới, các trạng thái phụ thuộc (mask con) đã được tính.
• Phép toán bitwise: Làm quen và sử dụng thành thạo các phép toán &, |, <<.
• INF: Khi tìm giá trị nhỏ nhất, sử dụng một giá trị INF đủ lớn nhưng cẩn thận để tránh tràn số khi cộng.
• Đếm bit 1: Hàm __builtin_popcount trong GCC/Clang giúp đếm số bit 1 hiệu quả, thường được dùng để xác định số lượng phần tử trong tập con hoặc chỉ số phần tử/công nhân tiếp theo.

Bài tập ví dụ:

Tổng số

Trong một buổi thiết kế thời trang, FullHouse Dev được giao một thử thách thú vị. Alice, một nhà thiết kế của nhóm, đang làm việc với một dãy số nguyên và muốn tạo ra một trò chơi với Bob để tìm cảm hứng cho bộ sưu tập mới của mình.

Bài toán

Alice được cho một mảng các số nguyên. Cô ấy chơi một trò chơi với Bob. Trong mỗi lượt, Alice chọn một đoạn con của mảng đã cho. Mỗi lượt, cô ấy phải chọn một đoạn con mới (nghĩa là có chỉ số bắt đầu hoặc kết thúc khác với các đoạn đã chọn trước đó).

Bob bắt đầu đếm các số tự nhiên từ đầu, tức là anh ấy nói \(1\), rồi \(2\) và tiếp tục. Alice dừng Bob lại ở số tự nhiên đầu tiên không xuất hiện trong đoạn con mà cô ấy đã chọn trong lượt này. Sau đó, cô ấy yêu cầu Bob viết tổng của tất cả các giá trị mà cô ấy đã dừng anh ấy lại. Bob không giỏi toán, bạn có thể giúp anh ấy không?

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(n\).
• Dòng tiếp theo chứa \(n\) số nguyên cách nhau bởi dấu cách, trong đó số thứ \(i\) biểu thị \(a_i\).

OUTPUT FORMAT:

• In ra một số nguyên duy nhất biểu thị kết quả yêu cầu.

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(1 \leq a_i \leq 100\)

Ví dụ

INPUT

3
1 2 3

OUTPUT

12

Giải thích

Vì Alice có thể chọn bất kỳ đoạn con nào theo bất kỳ thứ tự nào, ta hãy tìm câu trả lời cho từng đoạn con và cộng lại.

Mảng = \([1,2,3]\)

Trong đó \(a[i,j]\) biểu thị đoạn con bao gồm tất cả các phần tử trong khoảng từ \(i\) đến \(j\):

• \(a[1,1] = [1]\), số đầu tiên không xuất hiện là 2
• \(a[1,2] = [1,2]\), số đầu tiên không xuất hiện là 3
• \(a[1,3] = [1,2,3]\), số đầu tiên không xuất hiện là 4
• \(a[2,2] = [2]\), số đầu tiên không xuất hiện là 1
• \(a[2,3] = [2,3]\), số đầu tiên không xuất hiện là 1
• \(a[3,3] = [3]\), số đầu tiên không xuất hiện là 1

Vì vậy, đáp án là \(2 + 3 + 4 + 1 + 1 + 1 = 12\) Okay, đây là hướng dẫn giải bài "Tổng số" bằng C++ một cách ngắn gọn, tập trung vào ý tưởng chính mà không đưa ra mã nguồn hoàn chỉnh:

1. Hiểu bài toán: Cần tính tổng của "số dương nhỏ nhất không xuất hiện" (First Missing Positive - FMP) cho tất cả các đoạn con có thể có của mảng đầu vào.

2. Lặp qua tất cả các đoạn con:

   • Một mảng có n phần tử sẽ có n * (n + 1) / 2 đoạn con.
   • Bạn có thể duyệt qua tất cả các đoạn con bằng hai vòng lặp lồng nhau:
     • Vòng lặp ngoài chọn chỉ số bắt đầu i (từ 0 đến n-1).
     • Vòng lặp trong chọn chỉ số kết thúc j (từ i đến n-1).
   • Đoạn con hiện tại sẽ là từ a[i] đến a[j].

3. Tìm số dương nhỏ nhất không xuất hiện (FMP) cho mỗi đoạn con:

   • Đối với đoạn con a[i...j] hiện tại, bạn cần tìm số nguyên dương nhỏ nhất (1, 2, 3, ...) không có mặt trong đoạn con này.
   • Cách hiệu quả:
     • Sử dụng một mảng boolean (hoặc tập hợp băm) để đánh dấu sự hiện diện của các số. Kích thước của mảng boolean cần đủ lớn để kiểm tra các số dương, ví dụ, có thể kiểm tra tới n+1 hoặc một giá trị an toàn lớn hơn (ví dụ 102, dựa trên ràng buộc a_i <= 100 và FMP có thể lớn hơn n nhưng không quá lớn). bool da_co[k] với k là kích thước phù hợp.
     • Khởi tạo mảng boolean này với tất cả giá trị là false.
     • Duyệt qua các phần tử a[k] trong đoạn con a[i...j] (từ k=i đến j). Nếu a[k] là số dương và nằm trong phạm vi mảng boolean có thể đánh dấu, hãy đặt da_co[a[k]] = true.
     • Sau khi xử lý tất cả phần tử trong đoạn con, duyệt các số nguyên dương m bắt đầu từ 1 (m = 1, 2, 3, ...). Số m đầu tiên mà da_co[m] vẫn là false chính là FMP cho đoạn con này.

4. Tính tổng:

   • Khởi tạo một biến tổng (ví dụ: long long tong_ket_qua) ban đầu bằng 0.
   • Mỗi lần tìm được FMP cho một đoạn con, cộng giá trị FMP đó vào biến tổng.

5. Kết quả:

   • Sau khi duyệt và xử lý tất cả các đoạn con, giá trị cuối cùng của biến tong_ket_qua chính là đáp án cần in ra.

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