题解：P14568 【MX-S12-T3】排列

截至目前的最短解。

考虑从

1

到

n

依次确定每个数在

[1,i]

中的相对大小，那么每次可以在前

i-1

个数中的任意位置插入

a_i

。

如果

op_i=\{0,1\}

，那么我们确定

i

在前

i

个数中的是最大 / 最小的。

如果

op_i=\{2,3\}

，那么我们限制相当于以后的数比现在大 / 小。

记录一下当前剩下的空位个数即可。

设

f_{i,j}

表示考虑到前

i

个数，当前有

j+1

个空位的方案数，那么有转移：

f_{i,j}=f_{i-1,j-1},op_i=\{0,1\}

f_{i,j}=\sum_{k\ge j} f_{i-1,k},op_i=\{2,3\}

复杂度

O(n^2)

。

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,flag,a[5005],f[5005][5005],ans;
void add(int &a,int b){
	a+=b;
	a=(a>=mod?a-mod:a);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(a[i]==3 && a[j]==1) flag=true;
			if(a[i]==2 && a[j]==0) flag=true;
		}
	}
	if(flag){
		cout<<0;
		return 0;
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		if(a[i]==0 || a[i]==1) for(int j=1;j<=n;j++) add(f[i][j],f[i-1][j-1]);
		else for(int j=n;j>=0;j--) add(f[i][j],f[i][j+1]),add(f[i][j],f[i-1][j]);
	}
	for(int i=0;i<=n;i++) add(ans,f[n][i]);
	cout<<ans;
	return 0;
}

题解：P14568 【MX-S12-T3】排列

文章操作

相关推荐

评论

题解：P14568 【MX-S12-T3】排列