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

原文地址：https://blog.csdn.net/qq_74190237/article/details/142798321

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！