NOIP2023模拟5联测26 零二

本文主要是介绍NOIP2023模拟5联测26 零二，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

有一个长度为 $n$ 的序列 $A$ ，你可以将 $A$ 中的元素进行重排得到一个新的序列 $B$ ，规则如下：

令 $B$ 初始为空，同时维护一个初始为空的小根堆 $T$ ，然后进行以下两类操作各 $n$ 次：
- 将当前 $A$ 的第一个元素删除并加入小根堆 $T$ 中
- 将小根堆的堆顶删除并加入 $B$ 的末尾，需要保证 $T$ 非空

操作的顺序是任意的，问总共可能得到多少种不同的 $B$ ，输出答案模 $10^9+7$ 后的值。

$1\leq n\leq 100,1\leq A_i\leq n$

题解

注意到 $1\leq a_i\leq n$ ，我们先考虑如果 $A_i$ 是 $1$ 到 $n$ 的一个排列该怎么求解。

我们设 $n$ 在 $A$ 序列和 $B$ 序列中出现的位置分别为 $p, q$ ，即 $A_p=B_q=n$ 。因为 $T$ 是小根堆，且 $A$ 是 $1$ 到 $n$ 的一个排列，所以当拿出 $n$ 时就意味着 $T$ 已经被搬空了。由此可得， $B$ 的前 $q$ 个元素就是 $A$ 的前 $q$ 个元素，只是顺序可能不太一样。所以， $\{A_1,A_2,\dots,A_q\}=\{B_1,B_2,\dots,B_q\}$ ，且 $\{A_{q+1},A_{q+2},\dots,A_n\}=\{B_{q+1},B_{q+2},\dots,B_n\}$ 。

既然我们已经知道 $B_q=n$ ，那么我们可以把原问题看作两个子问题： $[1, q - 1]$ 和 $[q + 1, n]$ 。其中 $B_1,B_2,\dots,B_{q-1}$ 是由 $A_1,A_2,\dots,A_q$ 去掉 $A_p$ 再经过一些操作变化而来的，而 $B_{q+1},B_{q+2},\dots,B_n$ 是由 $A_{q+1},A_{q+2},\dots,A_n$ 经过一些操作变化而来的。

我们考虑递归地解决子问题。

因为在每次将一个问题分为子问题时都是将一个最大值删去，再分成两个部分，那么每个子问题所对应的子序列 $A^{'}$ 都是原序列 $A$ 的某一段区间 $[l, r]$ 删去一些较大的数而得到的。

我们考虑 $D P$ ，设 $f_{l,r,i}$ 表示 $A_l,A_{l+1},\dots,A_r$ 中不超过 $i$ 的数构成的子序列的方案数。设 $A_m=i$ ，下面考虑转移：

当 $m$ 不在 $[l, r]$ 上时，显然 $f_{l,r,i}=f_{l,r,i-1}$
当 $m$ 在 $[l, r]$ 上时，我们枚举 $i$ 在 $B$ 中的位置，可得
$f_{l,r,i}=\sum\limits_{x=m}^rf_{l,x,i-1}\cdot f_{x+1,r,i-1}$

那我们再来考虑如何处理 $A$ 不是 $1$ 到 $n$ 的排列的情况。

我们约定，当小根堆的堆顶为 $i$ ，并且堆中存在多个 $i$ ，那么我们取的时候先取下标最小的。

那在我们的约定下，可以将原数列转化为一个排列。

考虑这样转化的正确性。转化后 $A$ 中的数和 $B$ 中的数一一对应，而且 $B$ 中相同的数的先后顺序和在 $A$ 中的先后顺序是相同的，也就是说先后顺序一定，所以这样转化是可行的。

时间复杂度为 $O(n^4)$ ，这跑不满，是可以过的。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100;
const long long mod=1e9+7;
int n,a[N+5],b[N+5],cnt[N+5],rk[N+5];
long long f[N+5][N+5][N+5];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);++cnt[a[i]];}for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--){b[i]=cnt[a[i]]--;rk[b[i]]=i;}for(int i=1;i<=n+1;i++){for(int j=0;j<=n+1;j++) f[i][i-1][j]=1;}for(int l=n;l>=1;l--){for(int r=l;r<=n;r++){f[l][r][0]=1;if(b[l]<b[r])for(int i=1;i<b[r];i++) f[l][r][i]=f[l][r-1][i];elsefor(int i=1;i<b[l];i++) f[l][r][i]=f[l+1][r][i];for(int i=max(b[l],b[r]);i<=n;i++){if(rk[i]<l||rk[i]>r) f[l][r][i]=f[l][r][i-1];else{for(int j=rk[i];j<=r;j++){if(b[j]<=i)f[l][r][i]=(f[l][r][i]+f[l][j][i-1]*f[j+1][r][i-1])%mod;}}}}}printf("%lld",f[1][n][n]);return 0;
}