找啊找啊找GF

GitHub跳转原题关系图 Canvas 关系图返回列表

用二维 01 背包同时记录最多能泡到的 MM 数和对应的最少时间。

OJ: luogu

题目 ID: P1509

难度:普及/提高-

标签:动态规划01背包背包

日期: 2026-06-19 16:22

题意

有 n 个 MM，每个 MM 有三个属性：

需要花的钱 rmb_i
需要花的人品 rp_i
搞定她需要的时间 time_i

sqybi 只有 m 块大洋和 r 点人品。他想在不超过这两个限制的前提下，尽量多泡到 MM；如果能泡到的数量一样多，就希望总时间更少。

这张表把题意翻成了背包模型：

原题对象	背包含义
一个 MM	一个 0/1 物品
钱和人品	双重容量
泡到的数量	第一优先级
总时间	第二优先级

思路

一句话本质：二维费用的 01 背包，状态是 $(cnt, time)$ 二元组，先比人数再比时间。

先看最直接的暴力：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
mms = []
idx = 1
for _ in range(n):
    rmb, rp, time = data[idx], data[idx + 1], data[idx + 2]
    idx += 3
    mms.append((rmb, rp, time))
m, r = data[idx], data[idx + 1]

best_cnt = 0
best_time = 0
for mask in range(1 << n):
    cnt = 0
    tot_rmb = 0
    tot_rp = 0
    tot_time = 0
    for i in range(n):
        if mask >> i & 1:
            rmb, rp, time = mms[i]
            tot_rmb += rmb
            tot_rp += rp
            tot_time += time
            cnt += 1
    if tot_rmb <= m and tot_rp <= r:
        if cnt > best_cnt or (cnt == best_cnt and tot_time < best_time):
            best_cnt = cnt
            best_time = tot_time

print(best_time)

brute.py 枚举 $2^n$ 种选择，每个 MM 选或不选，检查两个资源限制，记录最优 $(cnt, time)$ 。 $n$ 最大 $100$ ， $2^{100}$ 不可能。

为什么一个人就对应一个 0/1 物品，却需要二维背包？

普通 01 背包只有一个容量（比如总钱数）。但这题有两个独立限制：钱 $m$ 和人品 $r$ 。选一个 MM 同时消耗两种资源，所以状态必须有两个维度。

两个目标（数量和时间）怎么比较？

先最大化 MM 数量，数量相同时最小化时间。这和普通 max 不同——不能只用一个大整数比较。需要把状态写成一个带优先级的 pair： $dp[j][k].cnt$ 越大越好， $cnt$ 相同时 $dp[j][k].time$ 越小越好。

转移时怎么判断"更优"？

设当前 MM 花费 $rmb_i$ 、 $rp_i$ 、 $time_i$ 。选她的候选状态是：

$cnt' = dp[j-rmb_i][k-rp_i].cnt + 1$
$time' = dp[j-rmb_i][k-rp_i].time + time_i$

如果 $cnt'$ 比当前 $dp[j][k].cnt$ 大，或者相等但 $time'$ 更小，就更新。两个容量 $j,k$ 都倒序枚举（因为每个 MM 只能选一次）。最终答案 $= dp[m][r].time$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#include <bits/stdc++.h>
using namespace std;

const int MAXR = 105;

struct State {
    int cnt;
    int time;
    State() : cnt(0), time(0) {}
    State(int c, int t) : cnt(c), time(t) {}
    bool better_than(const State& o) const {
        if (cnt != o.cnt) return cnt > o.cnt;
        return time < o.time;
    }
};

int n, m, r;
int rmb[105], rp[105], tmm[105];
// dp[a][b] 表示花 a 元 RMB、b 点 RP 时，能泡到的最多 MM 数及最少时间。
State dp[MAXR][MAXR];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> rmb[i] >> rp[i] >> tmm[i]; // 花费 RMB、RP，所需时间
    }
    cin >> m >> r;                         // 总 RMB 和总 RP

    // 0/1 背包：二维费用，倒序枚举两维。
    for (int i = 1; i <= n; i++) {
        for (int a = m; a >= rmb[i]; a--) {
            for (int b = r; b >= rp[i]; b--) {
                State nxt(dp[a - rmb[i]][b - rp[i]].cnt + 1,
                          dp[a - rmb[i]][b - rp[i]].time + tmm[i]);
                if (nxt.better_than(dp[a][b])) {
                    dp[a][b] = nxt;
                }
            }
        }
    }

    cout << dp[m][r].time << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nmr)$
空间复杂度： $O(mr)$

总结

这题本质上是二维 0/1 背包，只是比较方式不是单纯的“最大值”：

先比能选到的 MM 数量
再比总时间

遇到这种“先最大化数量，再最小化代价”的题，就可以把状态写成一个带优先级的 pair，然后做标准倒序 0/1 背包。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1509 找啊找啊找GF

题目背景

“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”

“诶，别再见啊…”

七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。

但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。

题目描述

sqybi 现在看中了 $n$ 个 MM，我们不妨把她们编号 $1$ 到 $n$ 。请 MM 吃饭是要花钱的，我们假设请 $i$ 号 MM 吃饭要花 $rmb_i$ 块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第 $i$ 号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费 $rp_i$ 的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞定她的时间，对于第 $i$ 个 MM 来说叫做 $time_i$ 。sqybi 保证自己有足够的魅力用 $time_i$ 的时间搞定第 $i$ 个 MM ^_。

sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。

sqybi 现在有 $m$ 块大洋,他也通过一段时间的努力攒到了 $r$ 的人品（这次为模拟赛出题也攒 rp 哦~~）。他凭借这些大洋和人品可以泡到一些 MM。他想知道，自己泡到最多的 MM 花费的最少时间是多少。

注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…

输入格式

输入的第一行是 $n$ ，表示 sqybi 看中的 MM 数量。

接下来有 $n$ 行，依次表示编号为 $1, 2, 3, \ldots , n$ 的一个 MM 的信息。每行表示一个 MM 的信息，有三个整数： $rmb$ ， $rp$ 和 $time$ 。

最后一行有两个整数，分别为 $m$ 和 $r$ 。

输出格式

你只需要输出一行，其中有一个整数，表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

sqybi 说：如果题目里说的都是真的就好了…

sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为 $0$ ），他要用这些时间出七夕比赛的题来攒 rp…

【数据规模】

对于 $20 \%$ 的数据， $1 \le n \le 10$ ；
对于 $100 \%$ 的数据， $1 \le rmb \le 100$ ， $1 \le rp \le 100$ ， $1 \le time \le 1000$ 。
对于 $100 \%$ 的数据， $1 \le m, r, n \le 100$ 。

找啊找啊找GF

目录

题意

思路

代码

复杂度

总结

一图流解析