首页 > 其他分享 >The 2021 Shanghai Collegiate Programming Contest D. Zztrans 的班级合照

The 2021 Shanghai Collegiate Programming Contest D. Zztrans 的班级合照

时间:2022-08-29 20:00:26浏览次数:95  
标签:Contest int rep Shanghai Programming long 第一排 dp define

计数dp好题

用组合数想了一下,需要容斥,情况太复杂
用计数dp,\(dp[i][j]\)表示前\(i\)个人有\(j\)个在第一排,并且按照身高遍历i,这样满足了第一个偏序关系(“排成人数相同的两排,每排从左向右身高都不递减”),然后只要保证第二排的人数少于等于第一排的人数,就能满足第二个偏序关系(“且第二排同学的身高不低于第一排对应位置同学的身高”)
状态转移很显然,就是加上所有的\(dp[i - v[i]][j - k]\),\(k\)是第一排的末尾有多少个当前身高的
最后统计答案还需要乘上对应的阶乘(dp过程只是保证了偏序关系,而次序可以交换)

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false),cin.tie(0);

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef unsigned long long ULL;

const int INF = 0X3f3f3f3f, N = 5000 + 10, MOD = 998244353;
const double eps = 1e-7, pi = acos(-1);

LL dp[N][N]; // dp[i][j] 前i个,j个在第一排 

int fact[N];

inline int add(int a, int b) {
	return (LL)a + b > MOD ? a + b - MOD : a + b;
}

void work() {
	int n;
	cin >> n;
	vector<int> c(n + 1), v;
	rep (i, 1, n) {
		int x;
		cin >> x;
		c[x]++;
	} 
	rep (i, 1, n) if (c[i]) v.push_back(c[i]);
	fact[0] = 1;
	rep (i, 1, n) fact[i] = (LL)fact[i - 1] * i % MOD;
	
	int sum = 0;
	dp[0][0] = 1;
	rep (i, 0, v.size() - 1) {
		sum += v[i];
		for (int j = min(n / 2, sum); j >= sum - j; j--) {
			for (int k = 0; k <= min(v[i], j); k++) {
				dp[sum][j] = add(dp[sum][j], dp[sum - v[i]][j - k]);
			}
		}
	}
	
	int res = dp[n][n / 2];
	rep (i, 0, v.size() - 1) res = (LL)res * fact[v[i]] % MOD;
	cout << res << endl;
	
}

signed main() {
	IO

	int test = 1;
//	cin >> test;

	while (test--) {
		work();
	}

	return 0;
}

标签:Contest,int,rep,Shanghai,Programming,long,第一排,dp,define
From: https://www.cnblogs.com/xhy666/p/16637176.html

相关文章

  • Educational DP Contest G - Longest Path
    目录题目思路代码题目给定一个有向无环图,叫你求图中的最长路径思路记忆化搜索,定义f[i]:表示从点i开始的最长路径长度,那么很容易得出转移方程为\(f_i=max(f_i,f_......
  • 【Virt.Contest】CF1155(div.2)
    CF传送门T1:ReverseaSubstring只有本身单调不减的字符串不能转换为字典序更小的字符串。否则肯定会出现\(s_i>s_{i+1}\)的情况。所以只要从头到尾扫一遍,找到\(s_i>......
  • AtCoder Beginner Contest 266 题解
    只有ABCDEFG的题解。A模拟。代码voidmian(){strings;cin>>s;intpos=int(s.size())/2;cout<<s[pos]<<endl;}B模拟,注意longlong。......
  • AtCoder Beginner Contest 266 D(DP)
    ……题面Takahashi要抓Snuke。好狠心的Takahashi呀(bushiSnuke有5个洞(,在$0m,1m,2m,3m,4m$处。Takahashi开始在$0m$处,每秒他能走$1m$。第$i......
  • AtCoder Beginner Contest 266 A-D
    AtCoderBeginnerContest266https://atcoder.jp/contests/abc266EF待补A-MiddleLetter输出字符串最中间的那个字母#include<bits/stdc++.h>usingnamespace......
  • 8.27训练赛(2018-2019, ICPC, Asia Yokohama Regional Contest 2018,gym102082)
    B一开始开题的时候想假了,以为用map存差的结果贪心就行了,实际上是一个比较妙的dp,用到了一个结论:两项就唯一确定一个等差数列。设\(f[i,j]\)表示最后两个数选了\(a_i\),\(a......
  • 【Virt.Contest】CF1321(div.2)
    第一次打虚拟赛。CF传送门T1:ContestforRobots统计\(r[i]=1\)且\(b[i]=0\)的位数\(t1\)和\(r[i]=0\)且\(b[i]=1\)的位数\(t2\)。两个数都为\(0\)或都为......
  • 【Virt.Contest】CF1215(div.2)
    第二次打虚拟赛。CF传送门T1:YellowCards黄色卡片中规中矩的\(T1\)。首先可以算出一个人也不罚下时发出的最多黄牌数:\(sum=a1*(k1-1)+a2*(k2-1)\)此时,若\(sum>=n......
  • AtCoder Beginner Contest 263(Java)
    A题桶排序1importjava.util.*;2publicclassMain{3publicstaticvoidmain(String[]args){4Scannersc=newScanner(System.in);5......
  • AtCoder Beginner Contest 265 D Iroha and Haiku (New ABC Edition)
    \(O{(n\logn)}\)做法我在考场上只想到此做法,不难想到,可以将三段用二分预处理。\(xs[i]\)表示从\(a_i\)开始总和为\(P\)的末尾编号,可以用二分处理。最后\(O(n)\)判......