Số đoạn thẳng tối đa độ dài a, b, c từ đoạn N trong C++

Cho đoạn thẳng dài N và ba độ dài a, b, c. Cắt đoạn N thành nhiều đoạn con nhất có thể, mỗi đoạn con chỉ được có độ dài a, b hoặc c.

Ví dụ

Input: N = 8, a = 3, b = 1, c = 2 → Output: 8 (8 đoạn độ dài 1)
Input: N = 13, a = 2, b = 7, c = 3 → Output: 6

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

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

Duyệt i từ 0 đến N-1, nếu dp[i] != -1 thì thử cắt thêm đoạn a, b, c: dp[i + len] = max(dp[i + len], dp[i] + 1) cho len ∈ {a, b, c} nếu i + len ≤ N.

Chương trình C++

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

int maxSegments(int N, int a, int b, int c) {
    vector dp(N + 1, -1);
    dp[0] = 0;
    for (int i = 0; i <= N; i++) {
        if (dp[i] == -1) continue;
        if (i + a <= N) dp[i + a] = max(dp[i + a], dp[i] + 1);
        if (i + b <= N) dp[i + b] = max(dp[i + b], dp[i] + 1);
        if (i + c <= N) dp[i + c] = max(dp[i + c], dp[i] + 1);
    }
    return dp[N];
}

int main() {
    int N = 13, a = 2, b = 7, c = 3;
    cout << maxSegments(N, a, b, c); // Output: 6
    return 0;
}

Kết quả

6

Lưu ý

• Nếu dp[N] == -1 → không thể cắt chính xác.
• Độ phức tạp O(N), rất nhanh.