Codeforces Round 946 E dp

题目在这里

题目大意: 一个人每月会有x的钱，m个月，每个月可以用钱换幸福值，问最多能获得幸福值多少,有多组测试

组数 : $1<t<1000$ $1<=x<=1e8$ $1<=m<=50$ 幸福值:$1<=h<=1000$ 数据总量$<=1e5$

分析: 简单的背包问题都是问什么设什么，但是这题$50\ast 1e8$显然是存不下的，考虑反过来设，设f[i]表示获得幸福值i的最小代价，转移方程就是:

$f[j]=min(f[j],f[j-h[i]]+c[i])$ $if(f[j-h[i]]+c[i]<=(i-1)\ast x)$ 即所需花费比我有的钱少

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int sum,m,x;
int c[1024],h[1024];
void solve(){
    sum = 0;
    cin>>m>>x;
    for(int i  = 1;i<=m;++i){
        cin>>c[i]>>h[i];
        sum+=h[i];
    }
    vector<int> f(sum+10,0x3f3f3f3f3f3f3f3f);//实现所需成本的最小花费
    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]!=0x3f3f3f3f3f3f3f3f){
            cout<<i<<"\n";
            return;
        }
    }
}
//赋值的正无穷太小导致WA了两发
signed main(){
    ios;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

好想学会dp