找啊找啊找GF 题目描述有点东西

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量
int n, m, r; // n表示物品MM数量，m表示有多少钱，r表示总人品
int rmb[110], rp[110], ti[110]; // rmb数组存储请每个MM吃饭要的钱，rp数组存储泡每个MM要的人品，ti数组存储搞定每个MM的时间
int dp1[110][110], dp2[110][110]; // dp1数组用于记录最大MM数量，dp2数组用于记录最小时间

int main() {
    // 输入MM数量n
    cin >> n;
    // 输入搞定每个MM的钱、人品和时间
    for (int i = 1; i <= n; i++) {
        cin >> rmb[i] >> rp[i] >> ti[i];
    }
    // 输入总金额m和总人品r
    cin >> m >> r;
    // 动态规划计算最大MM数量和最小时间
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= rmb[i]; j--) {
            for (int k = r; k >= rp[i]; k--) {
                // 如果当前组合的MM数量大于之前的组合
                if (dp1[j][k] < dp1[j - rmb[i]][k - rp[i]] + 1) {
                    // 更新最大MM数量
                    dp1[j][k] = max(dp1[j][k], dp1[j - rmb[i]][k - rp[i]] + 1);
                    // 更新最小时间
                    dp2[j][k] = max(dp2[j][k], dp2[j - rmb[i]][k - rp[i]] + ti[i]);
                }
                // 如果当前组合的MM数量等于之前的组合
                else if (dp1[j][k] == dp1[j - rmb[i]][k - rp[i]] + 1) {
                    // 更新最小时间
                    dp2[j][k] = min(dp2[j][k], dp2[j - rmb[i]][k - rp[i]] + ti[i]);
                }
            }
        }
    }
    // 输出结果：在给定总金额和总人品下，最小的时间
    cout << dp2[m][r] << endl;
    return 0;
}