AtCoder Beginner Contest 216（F）

F - Max Sum Counting

链接： F - Max Sum Counting

题意

两个 大小为 $n$ 的序列 $ai$ 和 $bi$，任意选取一些下标 $i$，求 $\max (ai)>=\sum bi$的方案数。

解析

首先考虑状态 一是和， 二是最大值， 但这样我们发现需要三重循环，在 $n=5000$ 的情况下是不能接受的复杂度，于是我们想到按 $ai$ 排序后，我们只计算 $\sum bi$ 的方案，将所有满足条件的方案再计入答案，就变成一个普通的背包求方案数了。

对于要按 $ai$ 排序的证明：
因为我们没有多开一维来记录 $\max (ai)$ 最大值， 所以对于每一种 $bi$ 和为 $sum$ 他的状态集合可能有许多不同的 $max(ai)$。
假设和为 $sum$ 有 $max(ai)=aj$，$maxai=ak$ 两种可能，若是不按 $ai$ 排序 会导致不知道 $aj,ak$ 那种状态可以转移。

假设 $sum=10$， $aj=100$ ，$ak=10$ 当前的 $ai=10$ ，$bi=10$ 那么只能从 $aj$ 转移 因为只有这种才保证 $\max (ai)>\sum bi$ 但已经把 $aj,ak$ 的状态整合在一起了不能分开。
若是按 $ai$ 排序，新来的 $ai$ 一定是目前的最大值, 一定比 $aj$ 和 $ak$ 都大 于是一个状态包含的所有情况都能转移。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010, mod = 998244353, MAX = 5000;
struct node{int ai, bi;bool operator < (const node &A)const{return ai < A.ai;}
}s[N];
int f[N];//bi之和价值为i的方案数
int main(){int n;cin >> n;for(int i = 1; i <= n; i ++) cin >> s[i].ai;for(int i = 1; i <= n; i ++) cin >> s[i].bi;sort(s + 1, s + 1 + n);f[0] = 1;int ans = 0;for(int i = 1; i <= n; i ++){for(int j = MAX; j >= s[i].bi; j --){f[j] = (f[j] + f[j - s[i].bi]) % mod;if(j <= s[i].ai) ans = (ans + f[j - s[i].bi]) % mod;}}cout << ans;return 0;
}