题解：CF1974E Money Buys Happiness

NyaingCBC · 2024-06-09 12:57:49 · 题解

思路分析

模型其实很简单，典型的背包，但是不同寻常的是其价值值域较小，而代价的值域偏大。

因此逆向思考，第二维用价值代替代价，求此时剩余的最大代价。如果这个值大于等于 0，那么意味着这个价值是可行的。

最后，用上背包常用的压维度，原地滚动就能过掉此题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n, m, dp[100005], l, r, sm;
signed main() {
    ios::sync_with_stdio(0);
    cin >> t;
    while (t--) {
        cin >> n >> m; sm = 0;
        memset(dp, 0xcf, sizeof dp);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> l >> r; sm += r;
            for (int j = sm; j >= 0; --j) {
                if (j >= r && dp[j - r] >= l)
                    dp[j] = max(dp[j], dp[j - r] - l);
                if (dp[j] >= 0) dp[j] += m;
            }
        }
        for (int i = sm; i >= 0; i--)
            if (dp[i] >= 0) {
                cout << i << endl; break;
            }
    }
    return 0;
}