An có một đoạn ruy băng độ dài n. Cậu muốn cắt chiếc ruy băng thành nhiều đoạn sao cho thỏa mãn điều kiện:

• Sau khi cắt mỗi đoạn ruy băng có độ dài a, b hoặc c.
• Sau khi cắt số đoạn ruy băng là nhiều nhất có thể.

Hãy giúp An cắt chiếc ruy băng nhé!

Input

Dòng đầu tiên chứa 4 số nguyên n, a, b và c (1 ≤ n, a, b, c ≤ 4000) — Độ dài ban đầu của ruy băng và độ dài cho phép của mỗi đoạn ruy băng sau khi cắt. Các số a, b và c có thể bằng nhau.

Output

In ra một số nguyên duy nhất - Số đoạn ruy băng nhiều nhất có thể cắt thỏa mãn.

Input                                                                         Output

5 5 3 2                                                                      2      

ngôn ngữ c++ ạ.Thank you

#include <bits/stdc++.h>
using namespace std;
long long n, a, b, c;
int main() {
    cin >> n >> a >> b >> c;
    vector<long long> dp(n + 1, -1);
    dp[0] = 0;
    for (long long i = 1; i <= n; ++i)
    {
        if (i >= a and dp[i - a] != -1)
        {
            dp[i] = max(dp[i], dp[i - a] + 1);
        }
        if (i >= b and dp[i - b] != -1)
        {
            dp[i] = max(dp[i], dp[i - b] + 1);
        }
        if (i >= c and dp[i - c] != -1)
        {
            dp[i] = max(dp[i], dp[i - c] + 1);
        }
    }
    cout << dp[n];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n,a,b,c;
    cin>>n>>a>>b>>c;
    vector<long long> l(n + 1, -1);
    l[0]=0;
    for (long long i=1;i<=n;++i) {
        if (i>=a && l[i-a]!=-1) 
        l[i]=max(l[i],l[i-a]+1);
        if (i>=b && l[i-b]!=-1) 
        l[i]=max(l[i],l[i-b]+1);
        if (i>=c && l[i-c]!=-1) 
        l[i]=max(l[i],l[i-c]+1);
    }
    cout<<l[n];
}