T2-8 找啊找啊找GF

题意理解

有 $n$ 个 MM，每个需要花费 $rmb[i]$ 块钱、$rp[i]$ 点人品、$time[i]$ 的时间。现有 $m$ 块钱和 $r$ 点人品，求：

1. 先最大化能泡到的 MM 数量
2. 在数量最多的前提下，最小化总时间

---

思路分析

这是二维费用背包问题，有两种费用（金钱、人品），需要同时优化数量和时间。

设 $dp[j][k]$ 表示：花费 $j$ 块钱和 $k$ 点人品能泡到的最多 MM 数量。

设 $t[j][k]$ 表示：在 $dp[j][k]$ 对应的最多数量下，花费的最少时间。

状态转移（01背包，逆序枚举）：

对于每个 MM，考虑选或不选：

• 如果选了能泡到更多 MM：更新数量和时间
• 如果数量相同：取时间更小的

边界条件：

• $dp[j][k] = 0$，$t[j][k] = 0$：初始泡 0 个 MM，花费 0 时间

答案： $t[m][r]$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;  // 最大数量

int n, m, r;                 // MM数量、金钱上限、人品上限
int rmb[MAXN], rp[MAXN], ti[MAXN];  // 每个MM的花费和时间
int dp[MAXN][MAXN];          // dp[j][k]表示花j块钱k点人品能泡到的最多MM数量
int t[MAXN][MAXN];           // t[j][k]表示对应数量下的最少时间

int main() {
    cin >> n;  // 读入MM数量
    
    for (int i = 1; i <= n; i++) {  // 读入每个MM的信息
        cin >> rmb[i] >> rp[i] >> ti[i];
    }
    
    cin >> m >> r;  // 读入金钱和人品上限
    
    for (int i = 1; i <= n; i++) {  // 枚举每个MM
        for (int j = m; j >= rmb[i]; j--) {  // 逆序枚举金钱
            for (int k = r; k >= rp[i]; k--) {  // 逆序枚举人品
                int newCnt = dp[j - rmb[i]][k - rp[i]] + 1;  // 选这个MM后的数量
                int newTime = t[j - rmb[i]][k - rp[i]] + ti[i];  // 选这个MM后的时间
                if (newCnt > dp[j][k]) {  // 能泡到更多MM
                    dp[j][k] = newCnt;
                    t[j][k] = newTime;
                } else if (newCnt == dp[j][k] && newTime < t[j][k]) {  // 数量相同，时间更少
                    t[j][k] = newTime;
                }
            }
        }
    }
    
    cout << t[m][r] << endl;  // 输出答案
    return 0;
}