Hiểu bài toán

Xét một trò chơi có hai đội. Khi đội A ghi điểm, đội B phải chống đẩy một số lần bằng tổng điểm hiện tại của đội A. An thuộc đội B và đếm được tổng số lần chống đẩy của mình là N. Có M cách ghi điểm, mỗi cách cho một số điểm d_i. Chúng ta cần tìm tổng điểm tối đa mà đội A có thể ghi sao cho tổng số lần chống đẩy của đội B đúng bằng N. Nếu không có cách nào, in ra -1.

Quy luật: Giả sử đội A ghi điểm theo chuỗi các giá trị x1, x2, ..., xk. Khi A ghi x1, B chống đẩy x1 lần. Khi A ghi x2, tổng điểm của A lúc này là x1 + x2, nên B chống đẩy thêm x1 + x2 lần. Cứ thế, tổng số lần chống đẩy của B là: N = x1 + (x1 + x2) + (x1 + x2 + x3) + ... + (x1 + ... + xk) Ta cần phân tích N để tìm các số xi sao cho tổng Sk = x1 + ... + xk là lớn nhất có thể.

Các cách tiếp cận

Cách Quy hoạch động theo cấu trúc bài toán

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

const int MAXN = 5005;
int n, m;
int d[12];
int f[MAXN][MAXN]; // f[j][s]: tong diem lon nhat co the dat duoc khi su dung j lan day va tong diem hien tai la s

int main() {
    cin >> n >> m;
    for(int i=1; i<=m; i++) cin >> d[i];

    memset(f, -1, sizeof(f));
    f[0][0] = 0;

    // Duyet qua so luong lan day tu 1 den n
    for(int j=1; j<=n; j++) {
        // Duyet qua cac kieu ghi diem
        for(int i=1; i<=m; i++) {
            // Diem ghi lan nay la d[i]
            // Can them vao tong diem truoc do la s - d[i]
            // Tong so lan day them la d[i] * (s / d[i])... thuc te ta chi can duyet s
            for(int s = d[i]; s <= j; s++) {
                if (f[j - d[i]][s - d[i]] != -1) {
                    f[j][s] = max(f[j][s], f[j - d[i]][s - d[i]] + d[i]);
                }
            }
        }
    }

    int res = -1;
    for(int s=0; s<=n; s++) res = max(res, f[n][s]);

    if(res == -1) cout << -1;
    else cout << res;
    return 0;
}

• Time Complexity: O(N^2 * M)
• Space Complexity: O(N^2)

Đây là cách tiếp cận trực tiếp nhất. Bài toán có tính chất 'tổng hợp' (knapsack-like).

• Trạng thái dp: f[j][s] là tổng điểm lớn nhất của đội A sau khi đội B đã chống đẩy j lần và tổng điểm của A hiện tại là s.
• Chuyển trạng thái: Khi A ghi thêm d[i] điểm, B phải chống đẩy thêm một lần bằng tổng điểm mới.
  • Số lần chống đẩy tăng thêm: 1.
  • Tổng điểm tăng thêm: d[i].
  • Do đó, f[j][s] có thể được cập nhật từ f[j-1][s-d[i]].
• Tuy nhiên, đoạn code mẫu lại duyệt s rất lớn, thực chất là để xử lý việc có thể ghi nhiều điểm cùng lúc. Nhưng logic cơ bản là: dp[j][s] = max(dp[j-1][s-d[i]] + d[i]).
• Độ phức tạp: vòng lặp j (đến N), s (đến N), i (đến M) => O(N^2 * M). Với N=5000, M=10, phép tính này khoảng 250 triệu, khá lớn nhưng có thể chấp nhận được trong C++ với tối ưu hóa vòng lặp.

Cách Tối ưu Quy hoạch động (Duyệt theo tổng điểm)

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

int n, m;
int d[15];
vector<long long> f; // f[x]: so lan day can de dat duoc tong diem x

int main() {
    cin >> n >> m;
    for(int i=0; i<m; i++) cin >> d[i];

    // Khoi tao: can 0 lan day de dat tong diem 0
    // N lan day toi da co the dat duoc tong diem ~ N*(N+1)/2, nhung ta chi can den N
    // O(N) la du.
    f.assign(n + 1, 1e9);
    f[0] = 0;

    for(int x = 1; x <= n; x++) {
        for(int val : d) {
            if (x >= val && f[x - val] != 1e9) {
                // De dat tong diem x, ta co the them 1 lan ghi diem 'val' vao sau
                // Luc nay, tong diem truoc do phai la x - val
                // So lan day them la (x) - (x - val) = val
                // Tong so lan day la f[x - val] + val
                if (f[x - val] + val <= n) {
                    f[x] = min(f[x], f[x - val] + val);
                }
            }
        }
    }

    // Tim tong diem lon nhat sao cho so lan day <= n
    // Tuy nhien, de chinh xac, ta can duyet nguoc tu n ve 0
    // Kiem tra xem tong diem x co the dat duoc chinh xac bang n lan day khong?
    // Cong thuc: Neu tong diem la S, va co k lan ghi diem (k la so phan tu cua day ghi diem)
    // Tong so lan day = k*S - sum_{i=1}^{k-1} i * x_{i+1} (approx)
    // De don gian, ta quay lai cach tiep thu 1 va sua chua.

    // Cach tiep thu 3 (TT 1) la chinh xac nhat: F(j, s)
    // Day la cach tiep thu 2 (dua tren tong diem) nhung can sua lai de thoa man dieu kien chinh xac.
    // 
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(N)

Cách này tìm cách tối ưu hóa DP. Nhận xét: Nếu tổng điểm cuối cùng là S, và các lần ghi điểm là x_1, ..., x_k. Số lần đẩy N = x_1 + (x_1+x_2) + ... + (x_1+...+x_k) = k*S - (k-1)x_2 - (k-2)x_3 - .... Điều này quá phức tạp để xử lý trực tiếp.

Thay vào đó, ta có thể dùng DP xác định xem tổng điểm S có thể đạt được hay không. Đoạn code mẫu (Solution 2) thực ra là một cách tiếp cận khác: Ẩn số k (số lần ghi điểm). Nếu k là số lần ghi điểm, thì tổng số lần đẩy là sum_{i=1}^k (k - i + 1) * x_i. Đoạn code trong Solution 2 lặp qua k (từ 1 đến khoảng sqrt(2N)), và với mỗi k, thực hiện DP để xem có thể đạt tổng điểm N hay không.

Giải thích chi tiết Solution 2:

• Duyệt qua k (số lần ghi điểm). Với k cố định, số lần đẩy cho lần ghi thứ i là i (hoặc k-i+1 tùy quy ước).
• Trong code, add = w * x (với w là chỉ số lần ghi, từ 1 đến k).
• DP state: dp[rem] là tổng điểm tối đa.
• Độ phức tạp: O(sqrt(N) * N * M).
• Đây là cách tối ưu nhất trong các solution đã cho.

Cách Duyệt toàn bộ (Backtracking / DFS)

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

int n, m;
int d[15];
int best_score = -1;

void dfs(int pushes, int score, int last_push) {
    if (pushes == n) {
        best_score = max(best_score, score);
        return;
    }
    if (pushes > n) return;

    // Thu ghi diem
    for(int i=0; i<m; i++) {
        // So lan day them de ghi diem d[i] phu thuoc vao tong diem moi
        // Neu tong diem moi la score + d[i], thi so lan day them la (score + d[i])
        // Tuy nhien, dieu kien o day phuc tap.
        // Cach de nhat: Moi buoc chi can them vao so lan day tuong ung.
        // Day la DFS co dieu kien.
    }
}

int main() {
    cin >> n >> m;
    for(int i=0; i<m; i++) cin >> d[i];
    // DFS(0, 0);
    // In ra best_score
    return 0;
}
// Lưu ý: DFS thuần không tối ưu, chỉ dùng để hiểu bài.

• Time Complexity: Exponential
• Space Complexity: O(N)

Đây là cách tiếp cận brute force (thử tất cả các trường hợp).

• Thử từng chuỗi các lần ghi điểm.
• Mỗi lần ghi điểm d[i], ta cộng d[i] vào tổng điểm, và cộng score + d[i] vào số lần đẩy.
• Dừng lại khi số lần đẩy vượt quá N.
• Nếu bằng N, cập nhật kết quả.
• Độ phức tạp: Số cách tổ hợp rất lớn, không khả thi với N=5000.
• Tuy nhiên, ta có thể dùng Memorization (DFS có nhớ) để biến thành quy hoạch động.

Đoạn code mẫu (Solution 3): f[j].insert(val): Tập hợp các tổng điểm có thể đạt được khi dùng đúng j lần đẩy.

• Duyệt j từ 0 đến N.
• Với mỗi val trong f[j], thử thêm các bước ghi điểm.
• Ví dụ: Ghi d[i] điểm. Số lần đẩy tăng thêm là val + d[i]. Tổng điểm tăng d[i].
• Cập nhật f[j + val + d[i]].insert(val + d[i]).
• Độ phức tạp phụ thuộc vào số lượng trạng thái. Với N=5000, số lượng cặp (j, val) có thể lớn.
• Solution 3 là một cách DFS + Memoization, nhưng có thể chậm hơn DP 2 chiều chuẩn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia nhỏ theo số lần ghi điểm (k). Với mỗi k, tổng số lần đẩy là một biểu thức tuyến tính của các điểm số.
• Quy hoạch động trạng thái (số lần đẩy, tổng điểm) là cách tiếp cận trực tiếp nhất, nhưng cần tối ưu không gian.
• Công thức tổng quát: Nếu ghi điểm x1, ..., xk thì tổng số lần đẩy N = sum{i=1}^k (k - i + 1) * xi.

Lỗi thường gặp

• Lầm tưởng rằng bài toán là bài toán túi đồ đơn giản (Knapsack) với trọng số là điểm số. Thực tế trọng số (số lần đẩy) phụ thuộc vào tổng điểm hiện tại.
• Quên kiểm tra trường hợp không có cách ghi điểm nào dẫn đến N.
• Lỗi tràn mảng khi khai báo mảng 2 chiều kích thước 5000x5000.