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

VP 获得

70

分，怎么回事呢。

永远不要忘记排列 DP 的两种状态维护方法——绝对大小和相对大小。

按值域 DP 没有什么前途，考虑按位置 DP，假设

[1,i]

已确定，注意到

op_{i+1}=2/3

时第

i+1

位填法有且仅有一种，且为当前未出现数字中最小/最大的一个，记

f_{i,j,k}

表示

[1,i]

中最小值为

j

最大值为

k

即可

O(n^3)

，如果只记录最小值可以做到

O(n^2)

并通过特殊性质 BC。

考虑特殊性质 A，不难发现答案恰好为

1

，原因是每一位与前面数字的相对大小固定，现在我们获得了

70

分。

我们刚刚设计状态时维护的是前面数字绝对大小的信息，考虑换一个思路，维护相对大小。

容易发现对于任意前缀，把

op\in \{0,1\}

的位置拿出来，它们的相对大小固定。

考虑此时插入一个

op=2

的数字，那么此时后面的数都必须大于这个数，因此相对大小比这个数小的位置就废掉了，这些数的绝对大小在此刻已经确定。

op=3

同理，因此令

f_{i,j}

表示

[1,i]

中有

j

个数字绝对大小未确定的方案数。

对于

op_{i+1}=0/1

，

f_{i,j}\to f_{i+1,j+1}

。

对于

op_{i+1}=2/3

，

f_{i,j}\to f_{i+1,x}\ (0\leq x\leq j)

。

但是这样是有漏洞的，如果

op

出现

31

或

20

子序列，我们的 DP 会默认

op=1/2

的位置可以填入数字，实际上是不行的，不难发现当且仅当出现这种情况时无解，直接特判输出

0

即可。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
void upd(ll &x,ll y){
	x=(x+y)%mod;
}
ll n,op[5005];
ll f[5005][5005],g[5005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>op[i];
	int b2=0,b3=0;
	for(int i=1;i<=n;i++){
		if(op[i]==2) b2=1;
		if(op[i]==3) b3=1;
		if(op[i]==0&&b2){
			cout<<"0\n";
			return 0;
		}
		if(op[i]==1&&b3){
			cout<<"0\n";
			return 0;
		}
	}
	if(op[1]==0||op[1]==1) f[1][1]=1;
	else f[1][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			upd(f[i][j],g[j]);
			upd(g[j+1],g[j]);
		}
		if(i==n) break;
		for(int j=0;j<=n;j++) g[j]=0;
		for(int j=0;j<=i;j++){
			if(op[i+1]==0||op[i+1]==1){
				upd(f[i+1][j+1],f[i][j]);
			}else{
				upd(g[0],f[i][j]);
				upd(g[j+1],mod-f[i][j]);
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=n;i++) upd(ans,f[n][i]);
	cout<<ans<<"\n";
}

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

文章操作

相关推荐

评论

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