很明显这是一道二维背包题目
如果一个dp数组做不了，那么我们就再来一个dp数组
题目要求，花费不超过 m ，消耗人品不超过 r ，泡到尽量多的妹子，时间尽量少
f [ i ][ j ] 花费不超过 m ，消耗人品不超过 j ，可以泡到的最多妹子数量
g [ i ][ j ] 花费不超过 m ，消耗人品不超过 j ，可以泡到最多妹子的最少时间
1. f [ i ][ j ] 可能相同但是对应的 g[ i ][ j ] 有不同，即
2. ans 可能相同但是对应的 g[ i ][ j ] 有不同，即
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=0; char last=‘ ‘,ch=getchar(); while(ch<‘0‘||ch>‘9‘) last=ch,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) ans=ans*10+ch-‘0‘,ch=getchar(); if(last==‘-‘) ans=-ans; return ans; } int n,m,r; int rmb[105],rp[105],tim[105]; int f[105][105],g[105][105]; int ans=0,res=2147483645; int main() { n=read(); for(int i=1;i<=n;i++) rmb[i]=read(),rp[i]=read(),tim[i]=read(); m=read();r=read(); for(int k=1;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]]+1>f[i][j]){ f[i][j]=f[i-rmb[k]][j-rp[k]]+1; g[i][j]=g[i-rmb[k]][j-rp[k]]+tim[k]; } if(f[i-rmb[k]][j-rp[k]]+1==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>214748364) { printf("0\n"); return 0; } printf("%d\n",res); return 0; }
原文：https://www.cnblogs.com/xiaoyezi-wink/p/12012134.html