Hiểu bài toán

Bạn cần chọn một dãy con liên tiếp các con bò sao cho độ dài dãy con không vượt quá K để tối ưu hóa tổng hiệu quả. Tuy nhiên, cách diễn đạt "không quá K con bò liên tiếp nhau" trong bài này thực chất là chọn một hoặc nhiều đoạn con liên tiếp, mỗi đoạn có độ dài tối đa K, và các đoạn này được ngăn cách nhau bởi ít nhất một con bò không được chọn. Mục tiêu là tìm cách chọn sao cho tổng hiệu quả là lớn nhất. Nói cách khác, ta cần tìm cách chia dãy ban đầu thành các đoạn con liên tiếp (mỗi đoạn độ dài từ 1 đến K) và chỉ lấy tổng của các đoạn con này (bỏ qua các phần tử ở giữa các đoạn).

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

Cách Quy hoạch động cơ bản

dp[i] = max(dp[j] + sum(j+1...i)) for i-K <= j < i

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

Đặt dp[i] là tổng hiệu quả lớn nhất có thể đạt được khi xét đến con bò thứ i (và con bò thứ i phải được chọn trong một đoạn con). Công thức truy hồi: dp[i] = max(dp[j] + (prefix[i] - prefix[j])) với j chạy từ i-K đến i-1. Ta có thể biến đổi: dp[i] = prefix[i] + max(dp[j] - prefix[j]). Với K nhỏ, cách này chạy tốt. Với K lớn (10^5), độ phức tạp O(N*K) sẽ không qua được do quá giới hạn thời gian.

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

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

int main() {
    int n, k; cin >> n >> k;
    vector<long long> a(n+1), prefix(n+1), dp(n+1);
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i-1] + a[i];
    }
    deque<int> dq;
    dp[0] = 0;
    dq.push_back(0);
    for(int i=1; i<=n; i++) {
        // Xóa các chỉ số nằm ngoài khoảng [i-k, i-1]
        while(!dq.empty() && dq.front() < i - k) dq.pop_front();

        // dp[i] là max(dp[j] + prefix[i] - prefix[j]) = prefix[i] + max(dp[j] - prefix[j])
        long long best_val = -1e18;
        if(!dq.empty()) best_val = dp[dq.front()] - prefix[dq.front()];

        // Nếu không chọn con bò i (tức là kết thúc đoạn trước đó)
        // Ta cần tính toán dp[i] là giá trị tốt nhất khi xét đến i
        // Tuy nhiên, bài này cho phép không chọn bò i. 
        // Công thức chuẩn: dp[i] = max(prefix[i] + max(dp[j] - prefix[j]), dp[i-1])
        // Hoặc coi dp[i] là max tổng khi xét đến i, không nhất thiết chọn i.
        // Nhưng lời giải trên codeforces/link là:
        // dp[i] = max(dp[i-1], prefix[i] + max_{j < i} (dp[j] - prefix[j]))
        // (với j phải thỏa mãn điều kiện đoạn)

        long long cand = (dq.empty() ? -1e18 : prefix[i] + dp[dq.front()] - prefix[dq.front()]);
        dp[i] = max(dp[i-1], cand);

        // Chuẩn bị cho các bước sau: dp[i] - prefix[i]
        long long val = dp[i] - prefix[i];
        while(!dq.empty() && (dp[dq.back()] - prefix[dq.back()]) <= val) dq.pop_back();
        dq.push_back(i);
    }
    cout << dp[n];
}

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

Để tối ưu hóa việc tìm max(dp[j] - prefix[j]) trong vòng lặp, ta sử dụng Deque (hoặc Priority Queue) để duy trì một cấu trúc dữ liệu cho phép truy vấn giá trị lớn nhất trong cửa sổ trượt [i-K, i-1] trong thời gian hằng số.

Cụ thể, ta cần tìm giá trị lớn nhất của biểu thức dp[j] - prefix[j] với j thuộc [i-K, i-1]. Deque sẽ lưu các chỉ số j sao cho các giá trị dp[j] - prefix[j] giảm dần. Khi duyệt đến i, ta:

1. Loại bỏ các j nằm ngoài khoảng cho phép (j < i-K).
2. Giá trị đầu tiên của deque chính là max của dp[j] - prefix[j] trong đoạn hợp lệ.
3. Tính dp[i] = max(dp[i-1], prefix[i] + max_val).
4. Thêm i vào deque, loại bỏ các phần tử ở cuối deque có giá trị nhỏ hơn hoặc bằng dp[i] - prefix[i].

Cách tiếp cận này biến độ phức tạp từ O(N*K) xuống O(N).

Cách Quy hoạch động với Priority Queue

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

typedef long long ll;

int main() {
    int n, k; cin >> n >> k;
    vector<ll> a(n+1), s(n+1), f(n+2), g(n+2);
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    priority_queue<ll> q1, q2;
    g[0] = 0;
    q1.push(g[0]);
    for(int i=1; i<=n+1; i++) {
        if(i - k - 1 >= 0) q2.push(g[i - k - 1]);
        while(!q1.empty() && !q2.empty() && q1.top() == q2.top()) {
            q1.pop(); q2.pop();
        }
        f[i] = q1.top() + s[i-1];
        g[i] = f[i] - s[i];
        q1.push(g[i]);
    }
    cout << f[n+1];
}

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

Đây là một cách tiếp cận khác sử dụng Priority Queue (Heap) để tìm max thay vì Deque.

Ta định nghĩa: f[i]: tổng hiệu quả lớn nhất khi xét đến con bò thứ i (và con bò thứ i được chọn). g[i] = f[i] - s[i]. Công thức: f[i] = max(g[j]) + s[i-1] với j chạy từ i-k đến i-1.

Sử dụng Max-Heap để lưu các giá trị g[j]. Heap cho phép truy vấn max trong O(log N). Tuy nhiên, ta cần loại bỏ các g[j] không còn nằm trong khoảng [i-k, i-1].

Giải pháp là sử dụng hai heaps: q1 (chứa các giá trị đang xét) và q2 (chứa các giá trị cần loại bỏ). Khi j bị loại ra khỏi cửa sổ (tức là i tăng lên), ta đẩy g[j] vào q2. Khi truy vấn max, ta so sánh đỉnh của q1 và q2; nếu chúng bằng nhau, ta loại bỏ cả hai (lazy deletion).

Cách này cũng có độ phức tạp O(N log N), chậm hơn một chút so với Deque nhưng vẫn chấp nhận được.

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

Bài học kinh nghiệm

• Biến đổi công thức quy hoạch động: dp[i] = max(dp[j] + prefix[i] - prefix[j]) thành dp[i] = prefix[i] + max(dp[j] - prefix[j]) giúp tách biệt phần phụ thuộc vào i (prefix[i]) và phần cần tối ưu (max(dp[j] - prefix[j])), từ đó có thể tối ưu bằng cấu trúc dữ liệu.
• Sử dụng Deque cho Sliding Window Maximum: Deque là cấu trúc dữ liệu tối ưu để tìm max/min trong một dãy con trượt với độ dài cố định hoặc giới hạn bởi chỉ số, cho phép thao tác trong thời gian O(1) trung bình.
• Mô hình hóa bài toán: Bài toán có thể xem là tìm đường đi ngắn nhất/tối ưu nhất trên đồ thị với các cạnh từ j đến i (i-K <= j < i) có trọng số là prefix[i] - prefix[j] + dp[j].

Lỗi thường gặp

• Lầm tưởng về điều kiện chọn bò: Nếu hiểu sai đề là chỉ được chọn đúng 1 đoạn liên tiếp độ dài <= K, đáp án sẽ sai. Đề bài cho phép chọn nhiều đoạn (được ngăn cách bởi bò không chọn).
• Xử lý biên: Cần chú ý các chỉ số j âm hoặc vượt quá n, và các giá trị âm (hiệu quả có thể là 0, nhưng dp cần khởi tạo giá trị âm rất lớn cho các trường hợp không thể chọn).
• Hiệu năng với K nhỏ: Nếu K rất nhỏ (ví dụ K=2), một giải pháp O(N*K) đơn giản có thể chạy nhanh hơn và dễ code hơn so với giải pháp phức tạp, nhưng với K lên tới 10^5, giải pháp O(N) hoặc O(N log N) là bắt buộc.