[NOIP 2024 模拟1]zyc大吃特吃
题意
给出两个序列 \(a,b\)，给出两个数 \(A,B\)。
求最多选出多少个数，使得刚好不满足 \(\sum a_i\le A\) 且 \(\sum b_i\le B\)。
思路
先考虑暴力 dp，定义 \(dp_{i,j}\) 表示选出的数 \(a\) 的和等于 \(i\)，选出的数 \(b\) 的和等于 \(j\)，最多选出的数的个数。转移就是普通的 01 背包，\(dp_{i,j}=\max dp_{i-a_k,j-b_k} + 1\)。
这样的时间复杂度是：\(O(nm^2)\)，不能通过。
我们可以换个角度，定义 \(dp_{i,j}\) 表示选出了 \(i\) 个数，\(a\) 和为 \(j\)，最小的 \(b\) 和。
为什么这样呢？因为固定了选出数的个数和 \(a\) 和，\(b\) 和一定越小越优。
转移也是普通的 01 背包，\(dp_{i,j}=\min dp_{i-1,j-a_k} + b_k\)。
时间复杂度：\(O(n^2m)\)，可以通过。
答案为 \(dp_{i-1,j}\le B\) 的最大 \(i\)，其中 \(j\le A\)。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105, M = 1e4 + 5;
int n, A, B, dp[N][M], ans;
struct dish {int a, b;};
dish x[N];
void solve() {
cin >> n >> A >> B;
for (int i = 1; i <= n; i ++) cin >> x[i].a >> x[i].b;
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i ++)
for (int j = n; j >= 1; j --)
for (int k = A; k >= x[i].a; k --)
dp[j][k] = min(dp[j][k], dp[j - 1][k - x[i].a] + x[i].b);
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= A; j ++)
if (dp[i][j] <= B) ans = max(ans, min(i + 1, n));
cout << ans << "\n";
}
signed main() {
freopen("eat.in", "r", stdin);
freopen("eat.out", "w", stdout);
int Case = 1;
// cin >> Case;
while (Case --)
solve();
return 0;
}