1 条题解

  • 0
    @ 2025-2-16 19:07:59
    #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; // 程序结束
    }
    
    
    • 1

    信息

    ID
    117
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    163
    已通过
    18
    上传者