题解：P14568 【MX-S12-T3】排列
george0929
·
·
题解
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_{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";
}
```