二维背包---P1509 找啊找啊找GF

P1509 找啊找啊找GF

题解

很明显这是一道二维背包题目

如果一个dp数组做不了,那么我们就再来一个dp数组

题目要求,花费不超过 m ,消耗人品不超过  r  ,泡到尽量多的妹子,时间尽量少

f [ i ][ j ] 花费不超过 m ,消耗人品不超过 j ,可以泡到的最多妹子数量

g [ i ][ j ] 花费不超过 m ,消耗人品不超过 j ,可以泡到最多妹子的最少时间

注意:

1. f [ i ][ j ] 可能相同但是对应的 g[ i ][ j ] 有不同,即

二维背包---P1509 找啊找啊找GF

2. ans 可能相同但是对应的 g[ i ][ j ] 有不同,即

二维背包---P1509 找啊找啊找GF

3.虽然上边说的差不多是一回事,但是还是提醒一句,这个人要泡到尽量多的妹子,而且他可能泡不到

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue> using namespace std; typedef long long ll; inline int read()
{
int ans=;
char last=' ',ch=getchar();
while(ch<''||ch>'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
} int n,m,r;
int rmb[],rp[],tim[];
int f[][],g[][];
int ans=,res=; int main()
{
n=read();
for(int i=;i<=n;i++) rmb[i]=read(),rp[i]=read(),tim[i]=read();
m=read();r=read();
for(int k=;k<=n;k++)
for(int i=m;i>=rmb[k];i--)
for(int j=r;j>=rp[k];j--){
if(f[i-rmb[k]][j-rp[k]]+>f[i][j]){
f[i][j]=f[i-rmb[k]][j-rp[k]]+;
g[i][j]=g[i-rmb[k]][j-rp[k]]+tim[k];
}
if(f[i-rmb[k]][j-rp[k]]+==f[i][j]){
g[i][j]=min(g[i][j],g[i-rmb[k]][j-rp[k]]+tim[k]);
}
if(f[i][j]==ans) res=min(res,g[i][j]);
if(f[i][j]>ans) ans=f[i][j],res=g[i][j];
}
if(res>) {
printf("0\n");
return ;
}
printf("%d\n",res);
return ;
}
上一篇:HDU.2111 Saving HDU(贪心)


下一篇:C# 基础问答