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 rmbrmbr p rprp和t i m e timetime。最后一行有两个整数分别为m mm和r rr。输出格式你只需要输出一行其中有一个整数表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。输入输出样例 #1输入 #14 1 2 5 2 1 6 2 2 2 2 2 3 5 5输出 #113说明/提示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≤1001 ≤ r p ≤ 100 1 \le rp \le 1001≤rp≤1001 ≤ 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提升数据读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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;cinn;for(i1;in;i)cinc[i]w[i]t[i];cinmr;for(i1;in;i)for(jm;jc[i];j--)for(kr;kw[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]/200001)*20000)-f[m][r]endl;return0;}
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 rmbrmbr p rprp和t i m e timetime。最后一行有两个整数分别为m mm和r rr。输出格式你只需要输出一行其中有一个整数表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。输入输出样例 #1输入 #14 1 2 5 2 1 6 2 2 2 2 2 3 5 5输出 #113说明/提示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≤1001 ≤ r p ≤ 100 1 \le rp \le 1001≤rp≤1001 ≤ 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提升数据读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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;cinn;for(i1;in;i)cinc[i]w[i]t[i];cinmr;for(i1;in;i)for(jm;jc[i];j--)for(kr;kw[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]/200001)*20000)-f[m][r]endl;return0;}
