返回题解分享
讨论 / 题解分享/ 帖子详情

拓拓的套餐 - 题解

#include <bits/stdc++.h> // 包含C++标准库中的所有头文件

const int MAX = 301; // 设置最大容量为 300 + 1

using namespace std; // 使用标准命名空间

pair<int, int> a[MAX]; // 定义pair数组a,用于存储食品的量
int f[MAX][MAX]; // 定义二维数组f,用于动态规划的状态转移

int main() { // 主函数入口
    int n, ft, sd, sum1 = 0, sum2 = 0; // 定义整型变量n、ft、sd和sum1、sum2,分别表示食品的种类、第一种食品的量、第二种食品的量以及两种食品的总量
    
    cin >> n; // 输入食品种类数
    cin >> ft >> sd; // 输入第一种食品和第二种食品的量

    for (int i = 1; i <= n; i++) { // 遍历每种食品
        cin >> a[i].first >> a[i].second; // 输入每种食品的量
        sum1 += a[i].first; // 统计第一种食品的总量
        sum2 += a[i].second; // 统计第二种食品的总量
    }

    if (sum1 < ft || sum2 < sd) { // 如果第一种或第二种食品的总量小于所需量
        cout << "-1" << endl; // 输出-1,表示无解
    } else {
        memset(f, 0x3f, sizeof f); // 将数组f初始化为最大值
        f[0][0] = 0; // 初始化f[0][0]为0

        for (int i = 1; i <= n; i++) { // 遍历每种食品
            for (int j = MAX - 1; j >= 0; j--) { // 遍历第一种食品的量
                for (int k = MAX - 1; k >= 0; k--) { // 遍历第二种食品的量
                    f[j][k] = min(f[j][k], f[max(0, j - a[i].first)][max(0, k - a[i].second)] + 1); // 更新状态转移方程
                }
            }
        }

        int ans = 0x3f3f3f3f; // 定义ans为最大值
        for (int i = ft; i < MAX; i++) { // 遍历第一种食品的量
            for (int j = sd; j < MAX; j++) { // 遍历第二种食品的量
                ans = min(ans, f[i][j]); // 更新最小值
            }
        }
        
        cout << ans << endl; // 输出最小解
    }

    return 0; // 程序结束
}
0 回复 0 转发 0 喜欢 7 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!