给你n物品，每个物品有a和b两个属性。你现在要挑选出一个集合S。
使得max ai >= sum(bi) {i ∈ S} （中文意思就是选一个集合，集合中所有物品属性a的最大值 大于等于 集合中所有物品b属性的和）
问你有多少种挑选方案。S不为空
模上998244353
首先对于模型 求挑选方案数，使得每个方案和 <= V 我们很容易就能知道这是一个背包的模型。
但是题目给这个模型加了一个限制。即选取方案里的最大值。才是你的V。
那么我们很容易就能想到先按a的值对这个物品进行sort。
这样的话我们就能枚举每一个物品作为V之后跑n2的背包。
但是这样的复杂度是n3的我们肯定不能接受。
于是考虑优化。
让我们仔细想想背包dp里的dp方程到底是什么意思
dp[在前 i 个物品中随便选取] [体积小于等于 j ]的方案数。
那么我们需要什么，需要的是dp [一定选取第 i 个物品， 并在前i - 1个物品随便选取 ] [体积小于等于 b[ i ] ]的方案数
可以容易想到的是如何优化第二维，就是先不管b的限制，在最后统计答案的时候只需要选取 dp[ i ] [0 - b[i] ]的方案数即可。
那么现在的dp方程已经被我们优化成 dp[ 一定选取第 i 个物品， 并在前i - 1个物品随便选取 ] [V = 5000]的方案
那么我们从最最开始的背包dp出发。
dp[ i - 1] [ j - v[ i ] ] ///其实代表的就是从前 i-1 个物品里随便选，并且一定要选 第 i 个物品的方案数。
那么我们只需要直接统计这个就好了！
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn = 5e3 + 10; const long long mod = 998244353; struct node { int a, b; }t[maxn]; long long dp[maxn]; bool cmp(node aa, node bb) { return aa.a < bb.a; } vector<int> st[maxn]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &t[i].a); } for(int i = 1; i <= n; i++) { scanf("%d", &t[i].b); } sort(t + 1, t + 1 + n, cmp); long long ans = 0; dp[0] = 1; for(int i = 1; i <= n; i++) { for(int j = t[i].b; j <= t[i].a; j++) { ans = (ans + dp[j - t[i].b]) % mod; } for(int j = 5000; j >= t[i].b; j--) { dp[j] = (dp[j] + dp[j - t[i].b]) % mod; } } printf("%lld\n", ans); }