[CodeForces 189 A]Cut Ribbon[dp][完全リュックサック]

タイトルリンク:[CodeForces 189 A]Cut Ribbon[dp][完全リュックサック]
题意分析:1本のリボンの长さnを与えて、リボンを所定の长さa、b、cの中の1种あるいは多种に切ることを要求して、闻きます:最大何本切ることができますか?(少なくとも1つの解が保証される)
问题の考え方:问题は実质的には:ちょうど完全なリュックサックをいっぱい入れて、入れることができる最大の価値はいくらですか?
个人感受:第一见题目の时、直接1つの阶段のdp方程式を书いて、サンプルがすべて过ごすことができないことを発见して、贪欲に考えて、それから各种...今日またこの问题を见て、やっと発见して、これは特に完全なリュックサックではありませんか...涙目になりました....
具体的なコードは以下の通りです.

#include<iostream>
#include<cstring>
using namespace std;

int dp[4011];

int main()
{
    int n, a[3];
    cin >> n >> a[0] >> a[1] >> a[2];
    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < 3; ++i)
        for (int j = a[i]; j <= n; ++j)
            dp[j] = max(dp[j], dp[j - a[i]] + 1);
    cout << dp[n] << '
';
    return 0;
}