Codeforces Round 946 (Div. 3) E. Money Buys Happiness

• $m$个月，每个月月底发$x$的薪水，也就是第$i$个月只能用前$i-1$个月挣的钱，而不能用这个月挣的钱。第$i$个月花费$c[i]$的薪水能获得$h[i]$的快乐度，问最多能获取的快乐度是多少。$m$和$h[i]$都较小

考虑01背包，设$dp[i]$表示获得快乐度为$i$的最小花费，$j$表示当前为第$j$个月份，那么有 d p [ i ] = m i n { d p [ i − h [ j ] ] + c [ j ] } , ( c [ j ] + d p [ i − h [ j ] ] ≤ ( j − 1 ) x ) dp[i]=min\{dp[i-h[j]]+c[j]\},(c[j]+dp[i-h[j]]\leq (j-1)x) dp[i]=min{dp[i−h[j]]+c[j]},(c[j]+dp[i−h[j]]≤(j−1)x)
也就是快乐度为$i$是通过快乐度为$i-h[j]$转移过来的，注意倒序枚举

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3f;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while(t--) {
    int m, x;
    cin >> m >> x;
    vector<ll> c(m + 1), h(m + 1);
    ll total = 0;
    for(int i=1;i<=m;i++) {
      cin >> c[i] >> h[i];
      total += h[i];
    }
    vector<ll> dp(total + 1, INF);
    dp[0] = 0;
    for(int j=1;j<=m;j++) {
      for(int i=total;i>=h[j];i--) {
        if(1ll * x * (j - 1) >= dp[i - h[j]] + c[j]) {
          dp[i] = min(dp[i], dp[i - h[j]] + c[j]);
        }
      }
    }
    int ans = 0;
    for(int i=total;i>=0;i--) {
      if(dp[i] != INF) {
        ans = i;
        break;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}