1 条题解
-
0
#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
- 上传者