算法
(二维费用背包) $O(NXY)$
记 dp[i][j][k]
表示在前 $i$ 份便当中买最少数量的便当使得章鱼烧至少有 $j$ 个且鲷鱼烧至少有 $k$ 个
转移方程:
不买下一份便当:
- $dp[i+1][j][k] = dp[i][j][k]$
买下一份便当:
- $dp[i+1][j+a][k+b] = \min(dp[i+1][j+a][k+b], dp[i][j][k] + 1)$
初始状态:
$dp[0][0] = 0$,其他值为无穷大
${\color{Red} {注意:}}$ $j + a$ 可能会远超过 $X$ 而造成浪费,所以应该取它和 $X$ 二者最小值,对于 $k + b$ 亦是如此,取它和 $Y$ 的最小值。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
int n, x, y;
cin >> n >> x >> y;
const int INF = 1001001001;
vector dp(x + 1, vector<int>(y + 1, INF));
dp[0][0] = 0;
rep(i, n) {
int a, b;
cin >> a >> b;
vector p(x + 1, vector<int>(y + 1, INF));
swap(dp, p);
rep(j, x + 1)rep(k, y + 1) {
chmin(dp[j][k], p[j][k]);
chmin(dp[min(j + a, x)][min(k + b, y)], p[j][k] + 1);
}
}
int ans = dp[x][y];
if (ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}