找啊找啊找GF

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

用二维 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 物品
钱和人品	双重容量
泡到的数量	第一优先级
总时间	第二优先级

思路

先看最直接的暴力：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#include <bits/stdc++.h>
using namespace std;

struct Girl {
    int money;
    int rp;
    int time;
};

int n, money, rp;
vector<Girl> girls;
vector<int> choose_girl; // choose_girl[i] = 0/1，表示第 i 个 MM 不选/选
int best_cnt = 0;
int best_time = 0;

void calc_state(int &cur_money, int &cur_rp, int &cur_cnt, int &cur_time) {
    cur_money = 0;
    cur_rp = 0;
    cur_cnt = 0;
    cur_time = 0;
    for (int i = 0; i < n; i++) {
        if (choose_girl[i] == 1) {
            cur_money += girls[i].money;
            cur_rp += girls[i].rp;
            cur_cnt++;
            cur_time += girls[i].time;
        }
    }
}

bool check() {
    int cur_money, cur_rp, cur_cnt, cur_time;
    calc_state(cur_money, cur_rp, cur_cnt, cur_time);
    return cur_money <= money && cur_rp <= rp;
}

void update_answer() {
    int cur_money, cur_rp, cur_cnt, cur_time;
    calc_state(cur_money, cur_rp, cur_cnt, cur_time);
    if (cur_money <= money && cur_rp <= rp) {
        if (cur_cnt > best_cnt || (cur_cnt == best_cnt && cur_time < best_time)) {
            best_cnt = cur_cnt;
            best_time = cur_time;
        }
    }
}

// dfs_choose 只负责枚举完整 01 序列。
void dfs_choose(int dep) {
    if (dep == n) {
        if (check()) {
            update_answer();
        }
        return;
    }

    // 第 dep 个 MM 的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_girl[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> n;
    girls.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> girls[i].money >> girls[i].rp >> girls[i].time;
    }
    cin >> money >> rp;

    choose_girl.assign(n, 0);
    dfs_choose(0);
    cout << best_time << '\n';

    return 0;
}

brute.cpp 把每个 MM 看成一个 01 选择：choose_girl[i] = 0/1 表示不选或选。递归先生成完整选择，叶子节点再检查金钱和 RP 是否超限，并统计能达到的最优数量和最少时间。

这个做法正确，但复杂度很高，只适合小数据验证。

关键观察是：

每个 MM 只能选一次，所以是 0/1 背包。
我们有两个限制：钱和人品。
目标不是单纯最大化时间或数量，而是先比数量，再比时间。

于是设：

dp[j][k] 表示钱不超过 j、人品不超过 k 时，能泡到的最多 MM 数量；
如果数量相同，就记录这组方案的最少时间。

这张表说明状态定义：

状态	含义
`dp[j][k]`	在钱、人品限制内的最优 `(数量, 时间)`

转移时，对于一个 MM：

不选她：状态保持不变
选她：数量加 1，时间加 time_i

因为每个 MM 只能选一次，所以钱和人品都要倒序枚举。

DP 公式

设 $dp_{j,k}$ 表示钱不超过 $j$ 、人品不超过 $k$ 时的最优二元组 $(cnt,time)$ ，其中 $cnt$ 越大越好， $cnt$ 相同时 $time$ 越小越好。处理第 $i$ 个 MM 时：

candidate=(dp_{j-rmb_i,k-rp_i}.cnt+1,\ dp_{j-rmb_i,k-rp_i}.time+time_i)

若 $candidate$ 按上述优先级更优，则更新：

dp_{j,k}\leftarrow candidate

两个容量都倒序枚举。最终查看 $dp_{m,r}$ 。

公式解释：状态值是一个带优先级的二元组，先比泡到的人数，再比总时间。选择当前 MM 时两个资源都要扣除，人数加一、时间增加；只有候选二元组更优才更新。

代码

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
48
49
50
51
52
53
54#include <bits/stdc++.h>
using namespace std;

struct State {
    int cnt;   // 能泡到的 MM 数量
    int time;  // 在该数量下的最少时间
};

static inline bool better(const State &a, const State &b) {
    if (a.cnt != b.cnt) return a.cnt > b.cnt;
    return a.time < b.time;
}

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

    int n;
    cin >> n;

    vector<array<int, 3>> girl(n);
    for (int i = 0; i < n; i++) {
        cin >> girl[i][0] >> girl[i][1] >> girl[i][2];
    }

    int money, rp;
    cin >> money >> rp;

    // dp[j][k]：在钱不超过 j、人品不超过 k 的前提下，最多能泡到多少 MM，
    //          如果数量相同，则取时间更少的方案。
    vector<vector<State>> dp(money + 1, vector<State>(rp + 1, {0, 0}));

    for (int i = 0; i < n; i++) {
        int need_money = girl[i][0];
        int need_rp = girl[i][1];
        int need_time = girl[i][2];

        // 0/1 背包：每个 MM 只能泡一次，所以容量倒序。
        for (int j = money; j >= need_money; j--) {
            for (int k = rp; k >= need_rp; k--) {
                State cand = dp[j - need_money][k - need_rp];
                cand.cnt++;
                cand.time += need_time;
                if (better(cand, dp[j][k])) {
                    dp[j][k] = cand;
                }
            }
        }
    }

    cout << dp[money][rp].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

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析