Codeforces Round 946 (Div. 3)

Shumian / 2024-10-13 / 原文

E. Money Buys Happiness

题意：给你$m$个月,每个月可以赚$x$元，每个月你都有一次机会花费$c_i$元，获得$h_i$的幸福。(当然你目前得有足够的钱)。求出能够获得的最大幸福值。
思路:我们可以求出获得$i$幸福值所需的最小花费，然后判断能否有足够的钱即可。考虑如何求解，把花费$c_i$看成物品价值，把$h_i$看成物品体积。那么容易发现，这个问题是一个$01$背包问题。那么状态转移就可以得到
f[j]=min(f[j],f[j-h[i]]+w[i])

代码

// Problem: E. Money Buys Happiness
// Contest: Codeforces - Codeforces Round 946 (Div. 3)
// URL: https://codeforces.com/contest/1974/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using ll=long long;
using i128=__int128;
typedef unsigned long long ull;
typedef pair<int, int> Pii;


const int Inf=0x3f3f3f3f;
void solve()
{
    ll m,x;cin>>m>>x;
    vector<ll>c(m+1),h(m+1);
    int ans=0; 
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        cin>>c[i]>>h[i];
        sum+=h[i];
    }
    vector<ll>f(sum+1,1e18);
    f[0]=0;
    for(int i=1;i<=m;i++)
        for(int j=sum;j>=h[i];j--)
        {
            if(f[j-h[i]]+c[i]<=(i-1)*x)
            f[j]=min(f[j],f[j-h[i]]+c[i]);
        }
        
    for(int i=sum;i>=0;i--)
    {
        if(f[i]<=(m-1)*x)
        {
            cout<<i<<endl;
            return;
        }
    }


}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _=1;cin>>_;while(_--)solve();
    return 0;
}