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;
}