- 线性dp
想到了排序a，以及背包，但是看了下数据范围以为不可以背包，但是可以发现 $\sum_{i \in S} \space b_i$ 不会大于5000，所以可以背包
不能只开一维dp数组，设置为一维会导致很多个第 i 位位置状态叠在一起
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;
const int N = 5e3 + 5;
const int mod = 998244353;
struct Node{
int x, y;
}a[N];
bool cmp(Node t1, Node t2){
return t1.x < t2.x;
}
//dp数组不能设置为一维，设置为一维会导致很多个第i位位置状态叠在一起
int f[N][N][2];
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i].x;
for(int i = 1; i <= n; i++) cin >> a[i].y;
sort(a + 1, a + 1 + n, cmp);
int ans = 0; f[0][0][0] = 1;
for(int i = 1; i <= n; i++) {
int val = a[i].y;
for(int j = 0; j <= 5000; j++) {
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mod;
if(j - val >= 0)f[i][j][1] = (f[i - 1][j - val][0] + f[i - 1][j - val][1]) % mod;
}
}
for(int i = 1; i <= n; i++) {
int val = a[i].y, maxn = a[i].x;
for(int j = val; j <= maxn; j++) {
ans = (ans + f[i][j][1]) % mod;
}
}
cout << ans << endl;
return 0;
}