题解：AT_abc216_f [ABC216F] Max Sum Counting

排序加背包

题目中最核心的条件:

其中 \max_{i \in S} a_i 这个条件，我们可以考虑对所有元素按 a 进行从小到大排序。

这样做的好处：

设当前扫的元素的 a 值为 a_i。

此时 a_i 一定是在已选中的元素形成的集合里的最大值，于是我们就可以直接愉快地对 a_i 统计答案啦。

至于为什么能想到这一步，道理也很简单：如果有一个 a 值更大的元素，加入集合，那此时集合就不会对当前扫到的 a_i 产生贡献了。

接下来贡献的计算我们可以使用背包来做：

设 dp[j] 表示当前所选元素形成的集合中，\sum_{i \in S} b_i=j 的方案数，那么往后扫的时候每次把 b_i 的贡献加进去就好了。

统计时遍历到体积 j，如果满足 a_i\geq j，那么说明满足条件。但我们如何保证 a_i 在当前的集合里呢？

最后一步小转换：只需统计 dp[j-b_i] 即可，代表着第 i 个元素存在于集合中时，能形成剩余体积的方案数。

总时间复杂度 O(n^2)。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n;
struct S{
	int a,b;
}s[5005];
int dp[5005];
int ans=0;
bool cmp(S x,S y){
	return x.a<y.a;
}
void xpigeon(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].a;
	}
	for(int i=1;i<=n;i++){
		cin>>s[i].b;
	}
	sort(s+1,s+n+1,cmp);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=5000;j>=s[i].b;j--){
			dp[j]=(dp[j]+dp[j-s[i].b])%mod;
			if(s[i].a>=j){
				ans=(ans+dp[j-s[i].b])%mod;
			}
		}
	}
	cout<<ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	xpigeon();
}