T1《Cờ Vây Đen Trắng》

Mô tả bài toán

Có một bàn cờ kích thước n×m, mỗi ô trên bàn cờ chứa một quân cờ đen hoặc trắng.

Bạn có thể thay đổi màu sắc của bất kỳ quân cờ nào (đổi từ đen sang trắng hoặc ngược lại). Mục tiêu là sử dụng số lần thay đổi tối thiểu để bàn cờ cuối cùng thỏa mãn:

• Bất kỳ hai quân cờ kề nhau (trên, dưới, trái, phải) đều có màu khác nhau.

Định dạng đầu vào

Dòng đầu tiên chứa hai số nguyên dương n và m, lần lượt là số hàng và số cột của bàn cờ. Tiếp theo là n dòng, mỗi dòng là một chuỗi độ dài m, trong đó 'B' đại diện cho quân cờ đen và 'W' đại diện cho quân cờ trắng.

Định dạng đầu ra

In ra một số nguyên, đại diện cho số lượng quân cờ cần thay đổi ít nhất.

Cách tiếp cận

Bàn cờ chỉ có thể có hai cấu trúc xen kẽ như sau:

B	W	B
W	B	W
B	W	B

W	B	W
B	W	B
W	B	W

Vì vậy, chúng ta chỉ cần tính toán số lần thay đổi cho cả hai trường hợp và chọn giá trị nhỏ hơn.

Một mẹo nhỏ: Vì hai cấu trúc này hoàn toàn khác nhau, tổng số quân cờ khác nhau giữa chúng và bàn cờ ban đầu bằng với tổng số quân cờ của bàn cờ ban đầu. Do đó, sau khi tính toán một trường hợp, chúng ta có thể lấy tổng số quân cờ của bàn cờ ban đầu trừ đi để tìm số quân cờ khác nhau của trường hợp còn lại.

Mã nguồn

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 1005;
char board[MAX_SIZE][MAX_SIZE];
int n, m;

int calculateChanges(char expectedColor) {
    int changes = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if ((i + j) % 2 == 0) {
                if (board[i][j] != expectedColor) changes++;
            } else {
                if (board[i][j] == expectedColor) changes++;
            }
        }
    }
    return changes;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    
    int changesBlackStart = calculateChanges('B');
    int changesWhiteStart = calculateChanges('W');
    
    cout << min(changesBlackStart, changesWhiteStart);
    return 0;
}

T2《Trò chơi Vượt ải》

Mô tả bài toán

Bạn đang chơi một trò chơi vượt ải. Nhân vật ban đầu có X điểm máu, sau mỗi ải, máu sẽ thay đổi (có thể tăng hoặc giảm).

Biết rằng khi máu của nhân vật nhỏ hơn hoặc bằng 0, nhân vật sẽ chết ngay lập tức. Bạn cần tính toán: điểm máu ban đầu X tối thiểu là bao nhiêu để đảm bảo vượt qua tất cả các ải.

Định dạng đầu vào

Dòng đầu tiên chứa một số nguyên dương n, đại diện cho số lượng ải.

Dòng thứ hai chứa n số nguyên a1, a2, ..., an, đại diện cho ảnh hưởng của mỗi ải đến máu (số dương là tăng, số âm là giảm).

Định dạng đầu ra

In ra một số nguyên, đại diện cho lượng máu ban đầu tối thiểu cần thiết để vượt qua trò chơi.

Cách tiếp cận

Bài toán này chỉ cần tìm giá trị máu thấp nhất tuyệt đối trong quá trình vượt ải cộng thêm 1, sử dụng tổng tiền tố (prefix sum).

Mã nguồn

#include <iostream>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    long long currentHealth = 0;
    long long minHealth = 0;
    
    for (int i = 0; i < n; i++) {
        long long change;
        cin >> change;
        currentHealth += change;
        minHealth = min(minHealth, currentHealth);
    }
    
    if (minHealth >= 0) {
        cout << 1;
    } else {
        cout << -minHealth + 1;
    }
    
    return 0;
}

Mở rộng

Khái niệm tổng tiền tố

Tổng tiền tố (Prefix Sum) là một kỹ thuật tiền xử lý được sử dụng để tính tổng của một khoảng trong mảng hoặc dãy số một cách nhanh chóng. Bằng cách tính toán và lưu trữ trước tổng từ vị trí bắt đầu đến mỗi vị trí, chúng ta có thể truy vấn tổng của bất kỳ khoảng nào trong thời gian hằng số.

Cài đặt tổng tiền tố

Trong C++, tổng tiền tố thường được lưu trữ trong một mảng bổ sung. Giả sử mảng ban đầu là arr, mảng tổng tiền tố là prefix, thì prefix[i] đại diện cho arr[0] + arr[1] + ... + arr[i-1].

Xây dựng mảng tổng tiền tố

vector<int> prefix(n + 1, 0); // Mảng tổng tiền tố thường có một phần tử nhiều hơn mảng ban đầu
for (int i = 1; i <= n; ++i) {
    prefix[i] = prefix[i - 1] + arr[i - 1];
}

Truy vấn tổng khoảng

Bằng mảng tổng tiền tố, tổng của khoảng [l, r] có thể được tính bằng cách:

int sum = prefix[r + 1] - prefix[l]; // Lưu ý sự dịch chuyển chỉ số

Ứng dụng tổng tiền tố

Tổng tiền tố thường được sử dụng để giải quyết các vấn đề cần truy vấn tổng khoảng thường xuyên, ví dụ như:

• Tính tổng của các mảng con.
• Vấn đề cửa sổ trượt.
• Đếm số lượng khoảng thỏa mãn điều kiện.

T3《Trộm Vàng》

Mô tả bài toán

Mỗi nhà đều chứa một số lượng vàng. Một tên trộm đang định trộm vàng, nhưng bạn biết rằng nếu trộm hai nhà kề nhau rất dễ bị phát hiện, vì vậy tên trộm quyết định trộm vàng từ các nhà không kề nhau.

Hiện đã biết mỗi nhà có bao nhiêu vàng, hãy tính toán số vàng tối đa mà tên trộm có thể trộm được.

Định dạng đầu vào

Dòng đầu tiên chứa một số nguyên, đại diện cho n nhà. Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an, lần lượt là số vàng của mỗi nhà.

Định dạng đầu ra

In ra một số nguyên, đại diện cho số vàng tối đa mà tên trộm có thể trộm được.

Cách tiếp cận

Đây là một bài toán quy hoạch động (DP) tiêu chuẩn và đơn giản.

Mã nguồn

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> gold(n);
    for (int i = 0; i < n; i++) {
        cin >> gold[i];
    }
    
    if (n == 0) {
        cout << 0;
        return 0;
    }
    
    if (n == 1) {
        cout << gold[0];
        return 0;
    }
    
    vector<long long> dp(n);
    dp[0] = gold[0];
    dp[1] = max(gold[0], gold[1]);
    
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + gold[i]);
    }
    
    cout << dp[n-1];
    return 0;
}

Mở rộng

Quy hoạch động trong C++

Quy hoạch động (Dynamic Programming, viết tắt DP) là một phương pháp giải quyết các vấn đề phức tạp bằng cách chia chúng thành các bài toán con và lưu trữ kết quả của các bài toán con để tránh tính toán lặp lại. Trong C++, quy hoạch động thường được triển khai bằng cách sử dụng mảng hoặc bảng để lưu trữ kết quả trung gian.

Các bước cơ bản của quy hoạch động

Xác định trạng thái và phương trình chuyển trạng thái. Trạng thái thường đại diện cho các bài toán con, phương trình chuyển trạng thái mô tả cách chuyển từ trạng thái này sang trạng thái khác.

Khởi tạo điều kiện biên. Điều kiện biên là điểm khởi đầu của quy hoạch động, thường là các bài toán con nhỏ nhất.

Lấp đầy bảng trạng thái bằng cách lặp hoặc đệ quy. Dựa trên phương trình chuyển trạng thái, tính toán dần các giải pháp của các trạng thái lớn hơn.

Các cách triển khai quy hoạch động phổ biến

Từ trên xuống (đệ quy có ghi nhớ) Sử dụng hàm đệ quy để giải quyết vấn đề và lưu trữ kết quả của các bài toán con đã tính bằng mảng hoặc bảng băm để tránh tính toán lặp lại.

int memo[MAX_N];
int dp(int n) {
    if (n == 0) return 0;
    if (memo[n] != -1) return memo[n];
    memo[n] = dp(n - 1) + dp(n - 2);
    return memo[n];
}

Từ dưới lên (phương pháp lặp) Bắt đầu từ các bài toán con nhỏ nhất và xây dựng dần các giải pháp của các bài toán con lớn hơn, thường sử dụng cấu trúc vòng lặp.

int dp[MAX_N];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

Kỹ thuật tối ưu hóa quy hoạch động

Tối ưu hóa không gian Trong một số trường hợp, chuyển trạng thái chỉ phụ thuộc vào một vài trạng thái trước đó, có thể giảm độ phức tạp không gian bằng cách sử dụng mảng lăn hoặc biến.

int a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
    int c = a + b;
    a = b;
    b = c;
}

Nén trạng thái Đối với các trạng thái có thể biểu diễn bằng bit, sử dụng phép toán bit để tối ưu hóa việc lưu trữ và chuyển trạng thái.

int dp[1 << N];
for (int mask = 0; mask < (1 << N); ++mask) {
    for (int i = 0; i < N; ++i) {
        if (!(mask & (1 << i))) {
            dp[mask | (1 << i)] = dp[mask] + cost[i];
        }
    }
}

Lưu ý khi sử dụng quy hoạch động

Đảm bảo tính đúng đắn của phương trình chuyển trạng thái. Phương trình chuyển trạng thái sai sẽ làm cho toàn bộ thuật toán quy hoạch động trở nên vô dụng.

Chú ý đến việc xử lý điều kiện biên. Điều kiện biên thường ảnh hưởng trực tiếp đến trạng thái ban đầu của quy hoạch động.

Xem xét độ phức tạp thời gian và không gian. Ưu điểm của quy hoạch động là tránh tính toán lặp lại, nhưng trong một số trường hợp cần tối ưu hóa việc sử dụng không gian.

T4《Tích Lớn Nhất》

Mô tả bài toán

Cho một dãy số nguyên độ dài n là a1, a2, ..., an.

Bạn có thể chia các số này thành hai nhóm (mỗi số phải và chỉ thuộc về một nhóm), gọi tổng của hai nhóm lần lượt là X và Y.

Bạn cần xuất ra giá trị X×Y lớn nhất.

Định dạng đầu vào

Dòng đầu tiên chứa một số nguyên n, đại diện cho độ dài dãy số. Dòng thứ hai chứa n số nguyên, đại diện cho a1, a2, ..., an.

Định dạng đầu ra

In ra một số nguyên, đại diện cho tích lớn nhất.

Cách tiếp cận

Đây cũng là một bài toán quy hoạch động.

Mã nguồn

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> numbers(n);
    int totalSum = 0;
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
        totalSum += numbers[i];
    }
    
    int halfSum = totalSum / 2;
    vector<int> dp(halfSum + 1, 0);
    
    for (int num : numbers) {
        for (int j = halfSum; j >= num; j--) {
            dp[j] = max(dp[j], dp[j - num] + num);
        }
    }
    
    int sum1 = dp[halfSum];
    int sum2 = totalSum - sum1;
    long long maxProduct = (long long)sum1 * sum2;
    
    cout << maxProduct;
    return 0;
}

T5《Kim Tự Tháp Số Nâng Cao》

Mô tả bài toán

Bạn còn nhớ bài toán kim tự tháp số chứ?

Bạn cần đi từ đỉnh (hàng 1 cột 1) đến hàng cuối cùng. Giả sử bạn đang ở hàng i cột j, bước tiếp theo chỉ có thể đi đến:

• Hàng i+1 cột j
• Hàng i+1 cột j+1

Mỗi khi đi đến một vị trí, bạn sẽ nhận được số ở vị trí đó.

Nhưng bây giờ bạn có một chiếc găng tay ma thuật: nó có thể làm gấp đôi số ở một vị trí bất kỳ. Thật tiếc, chiếc găng tay này chỉ có thể sử dụng tối đa k lần, nghĩa là bạn chỉ có thể sử dụng "gấp đôi" trên tối đa k vị trí trên đường đi.

Bây giờ bạn cần tính toán tổng số lớn nhất bạn có thể nhận được sau khi có găng tay ma thuật.

Định dạng đầu vào

Dòng đầu tiên chứa hai số nguyên dương n và k, lần lượt là số tầng của kim tự tháp và số lần tối đa phép sử dụng găng tay ma thuật. Tiếp theo là n dòng, dòng thứ i chứa i số nguyên, lần lượt là các số từ trái sang phải ở hàng i.

Định dạng đầu ra

In ra một số nguyên, đại diện cho tổng số lớn nhất có thể nhận được.

Cách tiếp cận

Đây là một bài toán quy hoạch động 3 chiều và là một bài toán knapsack 0/1.

Mã nguồn

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1003;
const int MAX_K = 11;

int n, k;
int pyramid[MAX_N][MAX_N];
long long dp[MAX_N][MAX_N][MAX_K];

int main() {
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> pyramid[i][j];
        }
    }
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int d = 0; d <= k; d++) {
                dp[i][j][d] = -1e18;
            }
        }
    }
    
    dp[1][1][0] = pyramid[1][1];
    dp[1][1][1] = pyramid[1][1] * 2;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int p = 0; p <= k; p++) {
                long long maxValue = -1e18;
                
                if (j > 1) {
                    maxValue = max(maxValue, dp[i-1][j-1][p] + pyramid[i][j]);
                    if (p > 0) maxValue = max(maxValue, dp[i-1][j-1][p-1] + pyramid[i][j] * 2);
                }
                
                if (j <= i-1) {
                    maxValue = max(maxValue, dp[i-1][j][p] + pyramid[i][j]);
                    if (p > 0) maxValue = max(maxValue, dp[i-1][j][p-1] + pyramid[i][j] * 2);
                }
                
                dp[i][j][p] = maxValue;
            }
        }
    }
    
    long long answer = -1e18;
    for (int j = 1; j <= n; j++) {
        for (int p = 0; p <= k; p++) {
            answer = max(answer, dp[n][j][p]);
        }
    }
    
    cout << answer;
    return 0;
}

Mở rộng

Vấn đề knapsack 0/1

Vấn đề knapsack 0/1 là một bài toán quy hoạch động kinh điển, yêu cầu trong một chiếc balo có dung lượng cho trước và một tập hợp các vật phẩm (mỗi vật phẩm có trọng lượng và giá trị), chọn các vật phẩm để xếp vào balo sao cho tổng giá trị lớn nhất. Mỗi vật phẩm chỉ có thể chọn hoặc không chọn (0 hoặc 1).

Giải pháp quy hoạch động

Nội dung cốt lõi của quy hoạch động là xác định trạng thái và phương trình chuyển trạng thái.

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

Dùng dp[i][j] để biểu thị giá trị lớn nhất khi chọn từ i vật phẩm đầu tiên, dung lượng balo là j.

Phương trình chuyển trạng thái

Đối với vật phẩm thứ i:

• Nếu không chọn vật phẩm thứ i, dp[i][j] = dp[i-1][j]
• Nếu chọn vật phẩm thứ i (yêu cầu j ≥ w_i), dp[i][j] = dp[i-1][j-w_i] + v_i

Kết hợp hai trường hợp: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i)

Khởi tạo

dp[0][j] = 0 (0 vật phẩm đầu tiên, giá trị là 0) dp[i][0] = 0 (dung lượng balo là 0, giá trị là 0)

T6《Du Lịch Thế Giới》

Mô tả bài toán

Bạn muốn đi du lịch vòng quanh thế giới. Hiện đã biết khoảng cách từ thành phố này đến thành phố khác (khoảng cách có hướng, có thể không đối xứng).

Bạn muốn xuất phát từ Thành phố 1 và tìm một tuyến đường ngắn nhất sao cho:

• Mỗi thành phố đều được đi qua chính xác một lần;
• Cuối cùng quay trở lại Thành phố 1.

Bạn cần xuất ra độ dài của tuyến đường ngắn nhất.

Định dạng đầu vào

Dòng đầu tiên chứa một số nguyên n, đại diện cho số lượng thành phố.

Tiếp theo là một ma trận n×n a, trong đó a[i][j] đại diện cho khoảng cách từ thành phố thứ i đến thành phố thứ j. Lưu ý: a[i][j] không nhất thiết bằng a[j][i].

Định dạng đầu ra

In ra một số nguyên, đại diện cho độ dài của tuyến đường ngắn nhất.

Cách tiếp cận

Đây là một bài toán quy hoạch động nén trạng thái.

Mã nguồn

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 20;
const int INF = 1e9;

int n;
int dist[MAX_N][MAX_N];
int dp[1 << MAX_N][MAX_N];

int main() {
    cin >> n;
    
    if (n == 1) {
        cout << 0;
        return 0;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INF;
        }
    }
    
    dp[1][0] = 0;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    int fullMask = (1 << n) - 1;
    int result = INF;
    
    for (int u = 1; u < n; u++) {
        result = min(result, dp[fullMask][u] + dist[u][0]);
    }
    
    cout << result;
    return 0;
}

Mở rộng

Quy hoạch động nén trạng thái (Dynamic Programming with State Compression) là một kỹ thuật tối ưu hóa được sử dụng để xử lý các bài toán quy hoạch động có không gian trạng thái lớn, bằng cách nén biểu diễn trạng thái để giảm bộ nhớ hoặc độ phức tạp tính toán. Dưới đây là các điểm chính về quy hoạch động nén trạng thái trong C++:

Ý tưởng cốt lõi của quy hoạch động nén trạng thái

Nén trạng thái thường sử dụng phép toán bit (như AND bit, OR bit, dịch bit) để chuyển đổi trạng thái đa chiều hoặc phức tạp thành một số nguyên (thường là dạng nhị phân). Ví dụ, dùng mỗi bit trong số nhị phân để biểu thị việc một vật phẩm được chọn hay một vị trí đã được thăm.

Các ứng dụng phổ biến

• Vấn đề người bán hàng du lịch (TSP): Dùng số nhị phân để biểu thị tập hợp các thành phố đã thăm.
• Vấn đề xếp hình trên bàn cờ: Dùng mặt nạ bit để biểu thị trạng thái xếp hình trên bàn cờ.
• Vấn đề tập con: Khi liệt kê tất cả các tập con, sử dụng trực tiếp mỗi bit trong số nhị phân làm dấu hiệu.

Điểm chính trong C++

1. Phép toán bit Các phép toán thường dùng bao gồm:

• Kiểm tra một bit có bằng 1 không: mask & (1 << i)
• Đặt một bit thành 1: mask |= (1 << i)
• Xóa một bit: mask &= ~(1 << i)
• Chuyển một bit: mask ^= (1 << i)

// Ví dụ: kiểm tra bit thứ i có bằng 1 không
bool isSet(int mask, int i) {
    return mask & (1 << i);
}

Thiết kế chuyển trạng thái Phương trình chuyển trạng thái thường liên quan đến việc tạo trạng thái mới từ trạng thái hiện tại (mặt nạ). Ví dụ trong TSP:

dp[mask][u] = min(dp[mask][u], dp[mask ^ (1 << u)][v] + dist[v][u]);

Khởi tạo và điều kiện biên Trạng thái ban đầu (như tập rỗng hoặc điểm xuất phát) cần được xử lý riêng:

// Khởi tạo: xuất phát từ thành phố 0
dp[1 << 0][0] = 0;

Thứ tự duyệt Thông thường, vòng lặp ngoài duyệt qua tất cả các trạng thái mặt nạ có thể, vòng lặp trong xử lý các bài toán con cụ thể:

for (int mask = 0; mask < (1 << n); ++mask) {
    for (int u = 0; u < n; ++u) {
        if (!(mask & (1 << u))) continue;
        // Logic chuyển trạng thái
    }
}

Kỹ thuật tối ưu hóa

• Tiền xử lý các trạng thái hợp lệ: Trước khi tạo tất cả các mặt nạ có thể, giảm tính toán không cần thiết.
• Mảng lăn: Đối với một số vấn đề, chỉ cần lưu trữ trạng thái trước đó.
• Cắt nhánh: Trong quá trình chuyển trạng thái, bỏ qua các nhánh không thể đạt được giải pháp tối ưu.

Ví dụ hoàn chỉnh (phần TSP)

const int INF = 1e9;
int dist[20][20];
int dp[1 << 16][20];

int tsp(int n) {
    memset(dp, INF, sizeof(dp));
    dp[1 << 0][0] = 0; // Xuất phát từ thành phố 0
    
    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int u = 0; u < n; ++u) {
            if (!(mask & (1 << u))) continue;
            for (int v = 0; v < n; ++v) {
                if (mask & (1 << v)) continue;
                dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], 
                                           dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // Trả về trạng thái cuối: đã thăm tất cả các thành phố và quay về điểm xuất phát
    int finalMask = (1 << n) - 1;
    int res = INF;
    for (int u = 1; u < n; ++u) {
        res = min(res, dp[finalMask][u] + dist[u][0]);
    }
    return res;
}

Lưu ý

• Phân tích độ phức tạp: Số trạng thái là O(2^n · n), phù hợp với n ≤ 20.
• Kỹ thuật gỡ lỗi: In ra trạng thái trung gian (dạng nhị phân của mặt nạ) để xác minh logic.

Bằng cách thiết kế hợp lý biểu diễn trạng thái và phương trình chuyển trạng thái, quy hoạch động nén trạng thái có thể cải thiện đáng kể hiệu suất giải quyết một số bài toán quy hoạch động.