$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题其实是二维费用的 01 背包，只不过在定义上面不一样

一般的背包的定义都是体积不超过 $j$ 或者体积恰好为 $j$

二者在初始化时，前者全部初始化为 0 ，后者初始化 $f[0][0]=0$

并且在体积的处理上，二者都不能为负数，因为无论是说体积「不超过」一个负数，还是说体积「恰好」为一个负数，都是没有意义的

这道题我们的定义为体积至少为 $j$，那么在初始化时，还是 $f[0][0]=0$，并且在体积的处理上，是允许出现负数的，因为体积「至少」为一个负数，只要当前体积为正数，那么都是满足的

举例来说，当前体积为 5 ，那么我可以说当前体积至少为 -5

也就是说，我们在枚举的时候需要将负数的部分也枚举到

在本题中，体积的最小取值为 1 ，因此体积为负数的情况等价与体积为 0 的情况

只要我选择了一个物品，那么体积必然是大于 1 的，如果出现了体积为 0 或者负数的情况，说明我没有选择任何一共物品

也就是说，体积为负数的情况和体积为 0 的情况是等价的

这道题的体积是二维的，我们状态压缩后采取从后往前遍历，即从最大值遍历到 0 ，如果出现负数的话将其映射到 0

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 50, M = 100;
int f[N][M];

int n, m, k;

int main()
{
    cin >> n >> m >> k;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;//记得要初始化
    while(k--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        for(int i = n; i >= 0; i--)
            for(int j = m; j >= 0; j--)
                f[i][j] = min(f[i][j], f[max(0, i - a)][max(0, j - b)] + c);
    }
    cout << f[n][m] << endl;
    return 0;
}