P1509 找啊找啊找GF【洛谷算法习题】
P1509 找啊找啊找GF
网页链接
P1509 找啊找啊找GF
题目背景
“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”
“诶，别再见啊…”
七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。
但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。
题目描述
sqybi 现在看中了n nn个 MM，我们不妨把她们编号1 11到n nn。请 MM 吃饭是要花钱的，我们假设请i ii号 MM 吃饭要花r m b i rmb_irmbi块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第i ii号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费r p i rp_irpi的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞定她的时间，对于第i ii个 MM 来说叫做t i m e i time_itimei。sqybi 保证自己有足够的魅力用t i m e i time_itimei的时间搞定第i ii个 MM_。
sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。
sqybi 现在有m mm块大洋,他也通过一段时间的努力攒到了r rr的人品（这次为模拟赛出题也攒 rp 哦~~）。他凭借这些大洋和人品可以泡到一些 MM。他想知道，自己泡到最多的 MM 花费的最少时间是多少。
注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…
输入格式
输入的第一行是n nn，表示 sqybi 看中的 MM 数量。
接下来有n nn行，依次表示编号为1 , 2 , 3 , … , n 1, 2, 3, \ldots , n1,2,3,…,n的一个 MM 的信息。每行表示一个 MM 的信息，有三个整数：r m b rmbrmb，r p rprp和t i m e timetime。
最后一行有两个整数，分别为m mm和r rr。
输出格式
你只需要输出一行，其中有一个整数，表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。
输入输出样例 #1
输入 #1
4 1 2 5 2 1 6 2 2 2 2 2 3 5 5输出 #1
13说明/提示
sqybi 说：如果题目里说的都是真的就好了…
sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为0 00），他要用这些时间出七夕比赛的题来攒 rp…
【数据规模】
对于20 % 20 \%20%的数据，1 ≤ n ≤ 10 1 \le n \le 101≤n≤10；
对于100 % 100 \%100%的数据，1 ≤ r m b ≤ 100 1 \le rmb \le 1001≤rmb≤100，1 ≤ r p ≤ 100 1 \le rp \le 1001≤rp≤100，1 ≤ t i m e ≤ 1000 1 \le time \le 10001≤time≤1000。
对于100 % 100 \%100%的数据，1 ≤ m , r , n ≤ 100 1 \le m, r, n \le 1001≤m,r,n≤100。
解题思路
本题是双费用双目标01背包问题，每个物品有金钱、人品两项花费约束，需要在花费不超限的前提下，优先最大化选取的英雄数量，数量相同时最小化总耗时。通过加权合并双目标的技巧，可将问题转化为标准二维费用背包求解。
1. 问题建模
- 每个MM对应一个可选物品，两项花费分别为金钱
rmb_i和人品rp_i，对应消耗为time_i。 - 优化目标分为两级：第一优先级是选取数量最多，第二优先级是总时间最少。
- 约束条件：总金钱不超过m，总人品不超过r。
2. 双目标加权合并技巧
由于两个目标有明确的优先级顺序，可以通过加权法将其合并为单个综合价值，最大化综合价值即可同时满足两个优先级：
构造综合价值公式：综合价值 = 选取数量 × 权重常数 - 总时间
其中权重常数必须大于最大可能的总时间，保证数量的权重永远高于时间的影响——数量多的方案综合价值一定更高；只有数量相同时，总时间更少的方案综合价值才更大。
本题中n≤100，单个时间≤1000，总时间最大为10^5，因此权重常数取大于1e5的值（如200000）即可完全保证正确性。代码中使用20000，在总时间不超过20000的场景下可正常运行。
3. 二维费用01背包实现
- 状态定义：
dp[j][k]表示花费j金钱、k人品时，能获得的最大综合价值。 - 初始状态：所有位置初始为0，对应选取0个物品、总时间为0的基准方案（0个物品对任意花费都成立）。
- 状态转移：对每个物品，倒序遍历金钱和人品两个维度（标准01背包倒序写法，保证每个物品仅被选取一次）：
d p [ j ] [ k ] = max ( d p [ j ] [ k ] , d p [ j − r m b i ] [ k − r p i ] + W − t i m e i ) dp[j][k] = \max(dp[j][k],\ dp[j-rmb_i][k-rp_i] + W - time_i)dp[j][k]=max(dp[j][k],dp[j−rmbi][k−rpi]+W−timei)
其中W为权重常数，+W对应选取数量加1，-time_i对应累加当前耗时。
4. 结果还原
设最终最大综合价值为val = dp[m][r]：
- 若
val == 0，说明无法选取任何MM，总时间为0。 - 否则，选取数量为
cnt = val / W + 1，总时间为cnt * W - val。
代码中的输出公式((val/W + 1) * W) - val就是该计算式的直接实现。
5. 复杂度分析
- 时间复杂度：O ( n × m × r ) O(n \times m \times r)O(n×m×r)，n、m、r均≤100，总运算量约百万级，完全适配1秒时间限制。
- 空间复杂度：O ( m × r ) O(m \times r)O(m×r)，二维DP数组空间开销极小。
总结
核心逻辑：将“优先最大化数量、再最小化时间”的双目标通过加权常数合并为单目标，转化为标准二维费用01背包问题，倒序枚举两个花费维度完成转移，最后从综合价值中还原出最小总时间。
关键操作：双目标加权合并、二维费用倒序转移、从综合值还原总时间。
效率保障：三层循环总规模仅百万级，运行速度极快。
代码简要说明
变量定义：
c[]存储每个MM的金钱花费，w[]存储人品花费，t[]存储所需时间。f[N][N]为二维DP数组，存储不同花费下的最大综合价值。
DP转移：
- 外层遍历每个MM，中层倒序遍历金钱（从m到c[i]），内层倒序遍历人品（从r到w[i]）。
- 转移时加上权重20000并减去当前时间，更新最大综合价值。
结果计算：
利用公式从最终综合价值中还原出总时间并输出。注意事项：
- 代码中权重20000在总时间超过20000时会出现精度偏差，实际应用中建议取更大的权重（如200000）保证正确性。
- 若无法选取任何MM，代码输出结果会等于权重值，需额外判断val是否为0，输出0以符合题目要求。
输入优化：关闭流同步并解绑tie，提升数据读取效率。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m,r;ll f[N][N],c[N],w[N],t[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll i,j,k;cin>>n;for(i=1;i<=n;i++)cin>>c[i]>>w[i]>>t[i];cin>>m>>r;for(i=1;i<=n;i++)for(j=m;j>=c[i];j--)for(k=r;k>=w[i];k--)if(f[j-c[i]][k-w[i]]+20000-t[i]>f[j][k])f[j][k]=f[j-c[i]][k-w[i]]+20000-t[i];cout<<((f[m][r]/20000+1)*20000)-f[m][r]<<endl;return0;}