dp入门 cf189A

题意：有一个长为n的带子，可以将它剪为a, b, c三种长度，问最多能剪多少段？

分析：是一道与完全背包类似的题，但这里要求的是背包正好装满。该怎么解决这一问题？我们可以将f数组全部初始化为-1，状态转移时如果上一个状态不是-1才可以转移。

状态转移方程\(f_{i, j}\)表示前i个物品恰好装满j的最大个数，\(f_{i, j} = max(f_{i, j - len[i]} + 1, \ f_{i - 1, j})\)当且仅当\(f_{i, j - len[i] }\ !=-1\)，降维，就是\(f_{j} = max(f_{j - len[i]} +1, \ f_{j})\) (和完全背包一样)，当长度为0时，最多只有0段，初始化f[0] = 0

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int mod = 998244353, INF = 1 << 30;
const int N = 4e3 + 10;
int f[N];
int len[5];


int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    std::cin >> n;
    for (int i = 1; i <= 3; i ++) cin >> len[i];
    sort(len + 1, len + 1 + 3);
    for (int i = 1; i <= n; i ++) f[i] = -1;
    f[0] = 0;
    for (int i = 1; i <= 3; i ++){
        for (int j = len[i]; j <= n; j ++) {
            if (f[j - len[i]] != -1){
                f[j] = max(f[j - len[i]] + 1, f[j]);
            }
        }
    }
    cout << f[n] << endl;
    return 0;
}