链接
题意:
给出你长度为 n n n的两个序列 a a a和 b b b,从中找出子集 S { 1 , 2 , 3 , 4 , . . . n } S\{1,2,3,4,...n\} S{1,2,3,4,...n}从中找子集然后要求
- m a x i ∈ S a i > = ∑ i ∈ S b i max_{i∈S}a_i>=\sum_{i∈S}b_i maxi∈Sai>=∑i∈Sbi
对方案数取模与 998244353 998244353 998244353
分析:
首先我们看数据范围是5000说明我们可以
O
(
N
2
)
O(N^2)
O(N2)
然后我们贪心的想先看
A
i
A_i
Ai比较小的,这样在看大的就不用看MAX,
然后我们对其按照 A i A_i Ai排序,然后就好想了, 枚举 [ b [ i ] , a [ i ] ] [b[i],a[i]] [b[i],a[i]]之间的数,这区间内 ∑ i ∈ S b i \sum_{i∈S}b_i ∑i∈Sbi 是符合条件的。
然后我们知道最大值是5000,所以就又用到了背包的思想。状态转移。我们可以用 d p [ i ] dp[i] dp[i]维护和为 i i i的方案数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct node {
ll x,y;
}q[maxn];
bool cmp(node a,node b){
return a.x<b.x;
}
ll dp[maxn];
ll n;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>q[i].x;
for(int i=1;i<=n;i++)cin>>q[i].y;
sort(q+1,q+1+n,cmp);
ll ans=0;
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=q[i].y;j<=q[i].x;j++){
ans=(ans+dp[j-q[i].y])%MOD;
}
for(int j=5000;j>=q[i].y;j--){
dp[j]=(dp[j]+dp[j-q[i].y])%MOD;
}
}
cout<<ans<<endl;
}
int main()
{
//init();
ll t = 1;
//scanf("%lld",&t);
while(t--)
{
solve();
}
return 0;
}