B.Blcoks(2019武大校赛现场赛)(吉比特杯第二届湖北省程序设计大赛) 解题报告 Apare_xzc

B.Blcoks(2019武大校赛现场赛)(吉比特杯第二届湖北省程序设计大赛) 解题报告

xzc 2019/4/16

题意：
  n个柱子(n<=20)，每个柱子有高度h和美丽值b,高度h各不相同，但b可能相同
  现在要选L个，高度升序，美丽值也升序，剩下的不能被看到要放在高度比它高的柱子的后面，求排列的种类数%998244353

输入形式：

n L
h1 h2 h3... hn
b1 b2 b3... bn

样例输入：

4 3
1 2 3 4
1 2 2 3

样例输出

3

思路：

• 2^20,dfs即可
• 先结构体按高度升序排
• 然后从高往低选，dfs选出L个
• 中间可以剪枝
• 如果一个块不选(第i个)，那么这个块可以放在所有比它高的柱子后面(n-i个，n-i种选择)
• 最后选够L个，若前面第1个到第x个还没选，那么这个选择的答案要乘以(n-1)*(n-2)*…*(n-x) 预处理前缀积即可(要取模)

我的代码:

#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 100;
const int mod = 998244353;
int b[maxn],m,n;
int r[maxn];
LL sum[maxn];
LL ans;
void dfs(int pre,int cnt,int x,LL preAns)
{
	if(cnt==m)
	{
		preAns = preAns*sum[x]%mod;
		ans = (ans+preAns)%mod;
		return;
	}
	if(m-cnt>x) return;
	if(b[pre]>b[x]) //可以选
	{
		r[cnt+1] = x;
		dfs(x,cnt+1,x-1,preAns);
	}
	dfs(pre,cnt,x-1,preAns*(n-x)%mod);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //frepen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    	vector<pair<int,int> > v(n);
    	For(i,0,n-1) scanf("%d",&v[i].first);
    	For(i,0,n-1) scanf("%d",&v[i].second);
    	sort(v.begin(),v.end());
    	For(i,1,n) b[i] = v[i-1].second; 
    	ans = 0;
    	sum[0] = 1;
    	For(i,1,n) sum[i] = sum[i-1]*(n-i)%mod;
    	r[1] = b[n];
    	dfs(n,1,n-1,1); 
    	printf("%lld\n",ans);
	}
    return 0;
}