E. Money Buys Happiness

题目链接：Problem - E - Codeforces

题目大意：

一开始你没有钱，每个月的末尾你会得到 x 英镑。在第 i 个月里，你可以付出 ci​ 英镑，获取 hi 的幸福。

在任何时刻你都不能欠钱，问你在 m 个月过后最多能获得多少幸福。

保证 ∑hi≤1e5。

输入：

第一行输入包含一个整数 t ( 1 ≤ t ≤ 1000 ) - 测试用例数。

每个测试用例的第一行包含两个整数 m 和 x ( 1≤m≤50 , 1≤x≤108 )--总月数和月薪。

下面 m 行的 i --包含两个整数 ci 和 hi ( 0≤ci≤1e8 , 1 ≤ hi ≤ 1e3 )-- i --月的费用和幸福。请注意，有些幸福可能是免费的( ci=0 为某些 i 的幸福)。

考察内容：              动态规划

1.首先观察题目的数据范围， 可以看出， 如果采用0-1背包，在1e8的范围，根本不可行。  题目给出 hi 的总和不超过1e5, 所以就将下标转换为 幸福值作为下标.

2.dp[ j ] 的含义，在买了 j 幸福过后剩余的钱。   此时不难想到，为了让后面的月份更有可能买， 所以因让dp[ i ] 保持当前状态最大。

3.dp方程：dp[j] = max(dp[ j ], dp[ j - a[ i ].second] - a[ i ].first);  其中采用了pair<int,int> 接受的， first代表  价格， second 代表 幸福。  

4.而此时方程可以转移的条件是：dp[j - a[ i ].second ] >= a[ i ].first, 要看之前的钱是否够。 最后发工资，注意：此处开始时初始化-1代表未到当前月份。 所以只给dp[ j ] >= 0的状态加上当前月份发的工资。    long long 不能忘

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;

void solve(){
    int n, x;
    cin >> n >> x;

    vector<pair<int,int>> a(n+1);
    int sum = 0;
    for(int i=1; i<=n; i++) {
        cin >> a[i].first >> a[i].second;
        sum += a[i].second;//算幸福，取下标，动态转移
    }

    vector<i64> dp(sum+1,-1);//开个long long
    dp[0] = 0; //第一个月为0元
    for(int i=1; i<=n; i++) {
        for(int j=sum; j-a[i].second >= 0; j--) { 
            if(dp[j-a[i].second] >= a[i].first)//买当前的幸福，看之前的状态可不可以买
                dp[j] = max(dp[j], dp[j-a[i].second] - a[i].first);
        }

        for(int j=0; j<=sum; j++) {
            if(dp[j] >= 0) {
                dp[j] += x;
            }
        }//发工资
    }
    for(int i=sum; i>=0; i--) { //下标就是幸福
        if(dp[i] >= 0) {
            cout << i << "\n";
            return;
        }
    }
}

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

感谢各位的点赞与观看， 欢迎大佬指正。