Tối đa hóa số đoạn cắt có độ dài p, q, r từ thanh dài L trong C++

Đề bài

Cho thanh dài L, cắt thành các đoạn chỉ có độ dài p, q, hoặc r. Tối đa hóa số đoạn.

Ví dụ: L=15, p=2, q=3, r=5 → 7 đoạn: {2,2,2,2,2,2,3}.

Thuật toán (Quy hoạch động)

dp[i] = số đoạn tối đa cho thanh độ dài i. Khởi tạo dp[0]=0, các giá trị khác = -1 (chưa đạt được).

Duyệt i từ 0 đến L: nếu dp[i] != -1, thử cắt thêm đoạn p, q, r: dp[i+p] = max(dp[i+p], dp[i]+1) (tương tự q, r).

Kết quả = dp[L].

Ví dụ minh họa (C++)

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

int getMaximumSegments(int L, int p, int q, int r) {
    vector<int> dp(L + 1, -1);
    dp[0] = 0;
    for (int i = 0; i <= L; ++i) {
        if (dp[i] == -1) continue;
        if (i + p <= L) dp[i + p] = max(dp[i + p], dp[i] + 1);
        if (i + q <= L) dp[i + q] = max(dp[i + q], dp[i] + 1);
        if (i + r <= L) dp[i + r] = max(dp[i + r], dp[i] + 1);
    }
    return dp[L];
}

int main() {
    int L = 15, p = 2, q = 3, r = 5;
    cout << "So doan toi da = " << getMaximumSegments(L, p, q, r) << endl;
    return 0;
}

Kết quả

So doan toi da = 7