CF E. Money Buys Happiness

原题链接:Problem - 1974E - Codeforces

题意:输入 T(≤1e3) 表示 T 组数据。所有数据的 hi 之和 ≤1e5。每组数据输入 n(1≤n≤50) x(1≤x≤1e8) 表示有 n 个月，每个月的月底你会得到 x 元钱。然后输入 n 行，每行两个数ci(0≤ci≤1e8) 和 hi(1≤hi≤1e3)，表示你可以在第 i 月的月初支付 ci 元钱，可以得到 hi 个单位的幸福。注意第 1 月你没有钱。注意 ci 可以等于 0，表示你可以免费获得 hi 的幸福。输出你能得到的幸福总量的最大值。

思路:dp.可以想到一个很直接的dp,01背包,dp[i][j]代表前i个数据花费j的代价得到的幸福值.因为每个月得到的钱可能很多,那么就不能直接开数组,如果使用map那么就会爆空间和时间.可以交换dp数组每个值的含义来优化,dp[i][j]代表前i个数据幸福值为j花费的代价.如果不可以购买那么dp[i][j]=dp[i-1][j],如果可以购买那么就是选择是否购买如果购买dp[i][j]=min(dp[i-1][j],dp[i-1][j-c]+h).

//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define endl '\n'
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
//gp_hash_table<ll,ll> op;
ll p[N],f[51][50010],q[N];
void Jiuyuan()
{ll n,k;cin>>n>>k;ll max1=0;for(int i=1;i<=n;i++){cin>>p[i]>>q[i];max1=max(max1,q[i]);}for(int i=max1*n;i>=0;i--)for(int j=0;j<=n;j++)f[j][i]=1e18;f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=max1*n;j++){if(j-q[i]>=0&&p[i]+f[i-1][j-q[i]]>(i-1)*k){f[i][j]=f[i-1][j];}else {if(j-q[i]>=0)f[i][j]=min(f[i][j],f[i-1][j-q[i]]+p[i]);f[i][j]=min(f[i-1][j],f[i][j]);}}}for(int i=max1*n;i>=0;i--){if(f[n][i]!=1e18){cout<<i<<endl;return;}}cout<<0<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--){Jiuyuan();}return 0;
}