题解
观察到h不大于1e5,于是拿h做文章
如果想要在第 \(i\) 个月的幸福值达到 \(j\) 那么第 \(i-1\) 个月的幸福值一定能达到 \(j-h_i\) 而且 \(cost_{[i-1][j-h_i]}+c_i \leq x·(i-1)\)
记得用滚动数组优化,因为这里 \(i\) 只和 \(i-1\) 的小幸福值有关
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll c[55]={0},h[55]={0};
ll dp[100005]={0};
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll t;
cin>>t;
while(t--)
{
ll m,x;
cin>>m>>x;
ll happy=0;
for(ll i=1;i<=m;i++)
{
cin>>c[i]>>h[i];
happy+=h[i];
}
for(ll j=0;j<=happy;j++) dp[j]=5e9+2;
dp[0]=0;
ll ans=0;
for(ll i=1;i<=m;i++)
{
for(ll j=happy;j>=h[i];j--)
{
if(x*(i-1)-dp[j-h[i]]>=c[i])
{
dp[j]=min(dp[j],dp[j-h[i]]+c[i]);
ans=max(ans,j);
}
}
}
cout<<ans<<"\n";
}
return 0;
}
标签:Money,ll,ans,cin,long,Happiness,Buys,dp
From: https://www.cnblogs.com/pure4knowledge/p/18206609