Hiểu bài toán

Người chơi bắt đầu tại vị trí 0 với tổng điểm 0. Mục tiêu là di chuyển sang phải các khoảng cách từ 1 đến K đơn vị để đến các vị trí từ 1 đến N. Khi đến vị trí i, người chơi nhận giá trị a_i. Người chơi có thể dừng lại bất cứ lúc nào. Cần tìm cách di chuyển để tổng điểm thu được là lớn nhất.

Quy hoạch động: Gọi dp[i] là tổng điểm lớn nhất có thể đạt được khi người chơi kết thúc hành trình tại vị trí i (và nhận ai). Khi đó, dp[i] = ai + max(dp[j]) với j chạy từ i-K đến i-1 (và j >= 0). Ngoài ra, cần xét trường hợp chỉ di chuyển một đoạn duy nhất từ 0 đến i, hoặc chỉ nhận a_i nếu các giá trị trước đó âm.

Đáp án cuối cùng là max(dp[i]) với i chạy từ 1 đến N.

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

Cách Quy hoạch động cơ bản (Brute Force)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int max(int a, int b){
    if (a > b) return a;
    else return b;
}

int main(void) {
    int N, K;
    scanf("%d%d", &N, &K);
    int *a = (int *)malloc((N+1) * sizeof(int));
    int *dp = (int *)malloc((N+1) * sizeof(int));
    dp[0] = 0;
    int i, j, maxx = INT_MIN;
    for (i = 1; i <= N; i++){
        scanf("%d", &a[i]);
    }
    for (i = 1; i <= N; i++){
        dp[i] = INT_MIN;
        for (j = 1; j <= K && i-j >= 0; j++){
            dp[i] = max(dp[i], dp[i-j] + a[i]);
        }
        maxx = max(maxx, dp[i]);
    }
    printf("%d", maxx);
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Dùng mảng dp[i] để lưu tổng điểm lớn nhất khi kết thúc tại vị trí i. Với mỗi vị trí i, ta duyệt lùi K bước về sau (từ i-1 đến i-K) để tìm điểm khởi tạo tốt nhất cho dp[i]. Công thức: dp[i] = max(dp[i], dp[i-j] + a[i]). Cuối cùng, duyệt lại mảng dp để tìm giá trị lớn nhất. Cách này chậm nếu K lớn, nhưng với K nhỏ (như trong bài này K=10) thì hoàn toàn chấp nhận được.

Cách Quy hoạch động tối ưu (Sliding Window)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    int *a = (int *)malloc((n + 1) * sizeof(int));
    long long *dp = (long long *)malloc((n + 1) * sizeof(long long));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    dp[0] = 0;
    long long max_val = -1e18;
    for (int i = 1; i <= n; i++) {
        long long best_prev = -1e18;
        // Tối ưu: tìm max(dp[j]) trong khoảng [i-k, i-1]
        for (int j = i - 1; j >= 0 && j >= i - k; j--) {
            if (dp[j] > best_prev) best_prev = dp[j];
        }
        dp[i] = best_prev + a[i];
        if (dp[i] > max_val) max_val = dp[i];
    }
    printf("%lld", max_val);
    return 0;
}

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

Cấu trúc tương tự cách 1, nhưng thay vì cộng dồn từng giá trị trong vòng lặp tính max, ta chỉ cần tìm giá trị lớn nhất của dp[j] trong K bước trước đó. Cách này giúp logic rõ ràng hơn và dữ liệu được lưu trữ chuẩn xác hơn (dùng long long để tránh tràn số nếu tổng điểm lớn). Trong trường hợp K lớn, ta có thể tối ưu thêm bằng Monotonic Queue để giảm độ phức tạp xuống O(N).

Cách Quy hoạch động với Monotonic Queue (Tối ưu)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXN 10005

int a[MAXN];
long long dp[MAXN];
int Q[MAXN]; // Queue lưu chỉ số
int head = 0, tail = 0;

long long max(long long a, long long b) {
    return a > b ? a : b;
}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &a[i]);
    }

    dp[0] = 0;
    long long ans = -1e18;

    // Khởi tạo queue cho dp[0]
    Q[tail++] = 0;

    for (int i = 1; i <= N; i++) {
        // Loại bỏ các chỉ số cũ ra khỏi cửa sổ K
        // Nếu Q[head] < i - K, thì chỉ số đó không thể nhảy tới i
        while (head < tail && Q[head] < i - K) {
            head++;
        }

        // Giá trị tốt nhất để nhảy tới i là dp[Q[head]]
        dp[i] = dp[Q[head]] + a[i];
        ans = max(ans, dp[i]);

        // Thêm dp[i] vào queue
        // Loại bỏ các phần tử xấu hơn dp[i] ở đuôi queue
        // (vì nếu dp[i] lớn hơn và tồn tại lâu hơn, nó sẽ luôn tốt hơn)
        while (head < tail && dp[i] >= dp[tail - 1]) {
            tail--;
        }
        Q[tail++] = i;
    }

    printf("%lld", ans);
    return 0;
}

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

Đây là phương pháp tối ưu nhất cho bài toán này. Thay vì duyệt K bước mỗi lần, ta sử dụng Monotonic Queue (Hàng đợi đơn điệu) để luôn duy trì giá trị dp lớn nhất trong cửa sổ trượt K phần tử.

• Queue lưu chỉ số j.
• Đầu queue (head) luôn là chỉ số có dp[j] lớn nhất trong cửa sổ hợp lệ.
• Khi di chuyển sang i, ta loại bỏ các chỉ số nằm ngoài khoảng [i-K, i-1].
• Khi thêm i vào queue, ta loại bỏ các chỉ số ở cuối queue mà dp của chúng nhỏ hơn dp[i] (vì i mới hơn và giá trị lớn hơn, nên chúng sẽ không bao giờ được dùng nữa). Độ phức tạp giảm từ O(N*K) xuống O(N).

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

Bài học kinh nghiệm

• Bài toán có tính chất quy hoạch động: tổng điểm tại vị trí i phụ thuộc vào K vị trí trước đó.
• Phải xử lý trường hợp không chọn gì (điểm 0) và chỉ chọn 1 phần tử (giá trị a_i) sao cho dp[0] = 0 và các dp khác khởi tạo âm vô cực.
• Giá trị N lên tới 10000, K lên tới 10, nên thuật toán O(N*K) (khoảng 100k phép tính) chạy rất nhanh. Nếu K lớn hơn, cần dùng Monotonic Queue để đảm bảo O(N).

Lỗi thường gặp

• Quên trường hợp người chơi chỉ di chuyển 1 bước (dp[i] = dp[0] + a[i] là hợp lệ).
• Tràn số khi tính tổng: N * max(a_i) = 10000 * 1000 = 10^7, vừa đủ cho int (2*10^9) nhưng nếu có âm và cộng dồn nhiều nên dùng long long cho an toàn.
• Lỗi truy cập mảng: Cần chú ý chỉ số j chạy từ i-1 về 0, không được vượt quá 0.