AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)

简介: AtCoder Beginner Contest 216 F - Max Sum Counting (降维 背包dp)

原题链接

题意:

给出你长度为n的两个序列a和b,从中找出子集S { 1 , 2 , 3 , 4 , . . . n } 从中找子集然后要求 m a x i ∈ S a i > = ∑ i ∈ S b i的种数。

思路:

首先,对于每个下标来说,有两个属性a , b。

按a从小到大排序后,枚举i,那么a i

就是当前的最大值,而∑ b i可以从[ 1 , i ]里取,而且b i必须取。

问题就转化成了从[ 1 , i − 1 ] 里面取任意个数使得他们的和小于等于a i − b i的方案数,可以用背包dp来解。

设d p [ j ]表示和为j方案数,那么答案就是a n s + = ∑ k = 0 a i − b i d p [ k ] 。

在求完之后,继续将b i 更新到d p里,便于下一次的转移。

时间复杂度O ( n 2 )

注意由于背包d p的状态是一维的,所以将b i更新到d p里的时候要倒着枚举。

代码:

// Problem: F - Max Sum Counting
// Contest: AtCoder - AtCoder Beginner Contest 216
// URL: https://atcoder.jp/contests/abc216/tasks/abc216_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
typedef pair<double, double>PDD;
#define I_int ll
inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
#define read read()
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
const int maxn=5e4+100;
int n;
struct node{
  int a,b;
}p[5100];
bool cmp(node a,node b){
  return a.a<b.a;
}
int dp[maxn];
int main() {
  n=read;
  rep(i,1,n) p[i].a=read;
  rep(i,1,n) p[i].b=read;
  sort(p+1,p+1+n,cmp);
  int ans=0,mod=998244353;
  dp[0]=1;
  rep(i,1,n){
    for(int j=0;j<=p[i].a-p[i].b;j++)
      ans=(ans+dp[j])%mod;
    for(int j=5010;j>=p[i].b;j--)
      dp[j]=(dp[j]+dp[j-p[i].b])%mod;
  }
  write(ans);
  return 0;
}


目录
相关文章
codeforces 285C - Building Permutation
题目大意是有一个含n个数的数组,你可以通过+1或者-1的操作使得其中的数是1--n中的数,且没有重复的数。 既然是这样的题意,那么我就应该把原数组中的数尽量往他最接近1--n中的位置放,然后求差绝对值之和,但有多个数,怎么使他们和最小,这样就要对其进行排序了,直接按大小给它们安排好位置,然后计算。
32 0
LeetCode 39. Combination Sum
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。
71 0
LeetCode 39. Combination Sum
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
115 0
|
机器学习/深度学习
AtCoder Beginner Contest 215 F - Dist Max 2 (二分 单调队列)
AtCoder Beginner Contest 215 F - Dist Max 2 (二分 单调队列)
132 0
AtCoder Beginner Contest 226 E - Just one(dfs求连通块 组合数学)
AtCoder Beginner Contest 226 E - Just one(dfs求连通块 组合数学)
103 0
|
人工智能 JavaScript BI
AtCoder Beginner Contest 222 D - Between Two Arrays(前缀和优化dp)
AtCoder Beginner Contest 222 D - Between Two Arrays(前缀和优化dp)
103 0
AtCoder Beginner Contest 221 D - Online games(差分 离散化 区间)
AtCoder Beginner Contest 221 D - Online games(差分 离散化 区间)
129 0