acwing 1020. 潜水员(背包求不少于问题)

题目链接

解题思路

  一开始想着体积和重量开大点枚举比v和m大的部分，结果各种超时。。。其实可以就按v和m枚举，枚举到0，减成负数就取0，也能表示超过v和m的情况。

代码

const int maxn = 1e3+10;
const int maxm = 1e5+10;
int n, v, m, a[maxm], b[maxm], c[maxm], dp[maxn][maxn];
int main() {
    IOS;
    clr(dp, 0x3f);
    cin >> v >> m;
    cin >> n;
    for (int i = 1; i<=n; ++i) cin >> a[i] >> b[i] >> c[i];
    dp[0][0] = 0;
    for (int i = 1; i<=n; ++i)
        for (int j = v; j>=0; --j)
            for (int k = m; k>=0; --k)
                dp[j][k] = min(dp[j][k], dp[max(0, j-a[i])][max(0, k-b[i])]+c[i]);
    cout << dp[v][m] << endl;
    return 0;