Codeforces Round 946 (Div. 3) E. Money Buys Happiness
- m m m个月，每个月月底发 x x x的薪水，也就是第 i i i个月只能用前 i − 1 i-1 i−1个月挣的钱，而不能用这个月挣的钱。第 i i i个月花费 c [ i ] c[i] c[i]的薪水能获得 h [ i ] h[i] h[i]的快乐度，问最多能获取的快乐度是多少。 m m m和 h [ i ] h[i] h[i]都较小
考虑01背包，设 d p [ i ] dp[i] dp[i]表示获得快乐度为 i i i的最小花费， j j j表示当前为第 j 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 i是通过快乐度为 i − h [ j ] i-h[j] 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;
}