算法
(01背包) $O(N * MX)$
先把两个数组按 $A$ 的大小从小到大排序
记 dp[i][j]
表示以第 $i$ 个数结尾的且 $B$ 的总和不超过 $j$ 有多少种取法
初始化:$dp[0][0] = 1, dp[0][1\sim] = 1$
为了节省空间,可以压掉第一维
转移方程:
dp[j + b] += dp[j]
当 $a \geq b$ 时,把 $dp[a - b]$ 加入答案
例子:
也就是前面所选元素的 $sum \leqslant 5 - 1 = 4$
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using P = std::pair<int, int>;
using mint = modint998244353;
int main() {
int n;
cin >> n;
vector<P> p(n);
rep(i, n) cin >> p[i].first;
rep(i, n) cin >> p[i].second;
sort(p.begin(), p.end());
const int MX = 5000;
vector<mint> dp(MX + 1, 1);
mint ans;
rep(i, n) {
auto [a, b] = p[i];
if (a >= b) ans += dp[a - b];
for (int j = MX - b; j >= 0; --j) {
dp[j + b] += dp[j];
}
}
cout << ans.val() << '\n';
return 0;
}