2 条题解

  • 0
    @ 2025-3-30 16:22:57
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 301;
    const int INF = 0x3f3f3f3f;
    pair<int, int> a[N];
    int f[N][N];
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n, x, y, sum1 = 0, sum2 = 0;
        cin >> n >> x >> y;
        for (int i = 1; i <= n; i++) {
            cin >> a[i].first >> a[i].second;
            sum1 += a[i].first;
            sum2 += a[i].second;
        }
        if (sum1 < x || sum2 < y) {
            cout << "-1\n";
            return 0;
        }
        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = x; j >= 0; j--) {
                for (int k = y; k >= 0; k--) {
                    int nj = max(0, j - a[i].first);
                    int nk = max(0, k - a[i].second);
                    f[j][k] = min(f[j][k], f[nj][nk] + 1);
                }
            }
        }
        cout << f[x][y] << "\n";
        return 0;
    }
    
    
    • 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
      难度
      8
      标签
      递交数
      286
      已通过
      35
      上传者