codeforces A -Cut Ribbon

思路

• 基础 $dp$ ，$d{p}_{i,j}$ 表示长度为 $i$ ， $piece$ 为 $j$ 的数量。题目范围 $4000$ 常规定义可能会 $MEL$ ，所以第二维为不同的 $piece$ 的个数。
• 枚举不同的 $pieces$ 长度。
• 方程：$d{p}_{i,j}=d{p}_{i?le{n}_j,j}+1/0$ 。（是当前枚举长度则为 $1$ )

Think Twice, Code Once

signed main() {

    int T = 1;
//    T = read();
    while (T--) {
        int n = read();
        vector<int> vec;
        for (int i = 1; i < 4; ++i) {
            int u = read();
            vec.push_back(u);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        vector<vector<int>> dp(4000 + 10, vector<int>(vec.size()));
        auto get_sum = [&] (int j) {
            int res = 0;
            for (int i = 0; i < vec.size(); ++i) res += dp[j][i];
            return res;
        };
        for (int i = 0; i < vec.size(); ++i) dp[vec[i]][i] = 1;
        for (int i = 1; i <= n; ++i) {
            int sum = 0;
            for (int j = 0; j < vec.size(); ++j) {
                if (i - vec[j] >= 0) {
                    int tmp = get_sum(i - vec[j]);
                    if (sum < tmp) {
                        sum = tmp;
                        for (int k = 0; k < vec.size(); ++k) dp[i][k] = dp[i - vec[j]][k] + (k == j);
                    }
                }
            }
        }
        write(get_sum(n));
    }
    return 0;
}
//3119 3515 1021 7