人才出题人,挺会整活的。。。
一眼二维费用背包。
题目要求不单单是求最小时间,还要保证MM数量最多。
需要开两个数组f,dp,分别代表给定人品,钱能get到的最多MM数量,确保最多数量下的最少时间花费。
将人品,钱作为两个限制维度,将每个MM数量视作1,走背包f,更新f的同时去更新dp。
#include<bits/stdc++.h>
using namespace std;
const int N=300;
int f[N][N],a[N],b[N],c[N],dp[N][N];//f 能get的最多MM, dp 数量最多的情况下最少时间花费
signed main()
{ int n; cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];int x,y,z; cin>>x>>y;for(int i=1;i<=n;i++){for(int j=x;j>=a[i];j--) for(int k=y;k>=b[i];k--){if(f[j][k]<f[j-a[i]][k-b[i]]+1)//能泡到更多就泡,同时更新时间花费 {f[j][k]=f[j-a[i]][k-b[i]]+1;dp[j][k]=dp[j-a[i]][k-b[i]]+c[i];}else if(f[j][k]==f[j-a[i]][k-b[i]]+1)//数量相同看时间能否更少 {dp[j][k]=min(dp[j-a[i]][k-b[i]]+c[i],dp[j][k]);}}}cout<<dp[x][y];
}
24/8/30 距离开学只剩2天😣😔😲🙂↔️