[DP记录]AT2366 [AGC012F] Prefix Median

**题意** ： 给定一个长为 $2n-1$ 的序列 $a$ ，定义中位数序列 $b={\rm midsq}(a)$ 如下 ： - $|b|=n$ - $b_i=\{a_1,a_2,...,a_{2i-1}\}$ 的中位数。 给出序列 $a$ ，可以将其任意打乱，问能产生多少个本质不同的 ${\rm midsq}(a)$。 答案对 $10^9+7$ 取模。 $n\leq 50$ ，时限$\texttt{2s}$。 ------------ AGC 的计数日常 ： 这也能数？？？ - 先考虑 $a$ 中没有重复元素的情况，即 $a_i=i$。 先来考察怎样的 $b$ 是可能被生成的。 生成 $b={\rm midsq}(p)$ 的方法可以理解为 ，先令 $b_1=p_1$ ，然后每插入两个 $p$ 就将 $b$ 重新设置为当前的中位数。 在求解 $b_i$ 时，若插入的两个数字都比 $b_{i-1}$ 大，则中位数会变为 $b_{i-1}$ 的后继，若都比 $b_{i-1}$ 小，则变为其前驱，一大一小则不变。 最终，$b_n$ 会等于整个 $a$ 序列的中位数。 - $b_i$ 是 $p_{1\sim i}$ 中 $b_{i-1}$ 的前驱或后继，或等于 $b_{i-1}$。 等价于 ： 对于任意的 $j<i$ 都**不满足** $b_i<b_j<b_{i+1}$ 或 $b_{i+1}<b_j<b_i$ 。 然而，某些时候并不能找出“两个比 $b_{i-1}$ 大/小” 的数字。因此，无法总是做到向 前驱/后继 移动。 根据这个限制，可以发现 $i\leq b_i\leq 2n-i$。 这两个条件配合在一起，正是 $b$ 序列能被生成的**充要条件**。 - 充分性（简略）证明 对于在 $b$ 中没有出现的 $a$ 中元素，记为集合 $S$。 构造时，若 $b_i=b_{i-1}$ ，则从 $S$ 中拿出最小值 $u$ 和最大值 $v$。 若 $b_i<b_{i-1}$ ，则加入 $b_i$ ，并从 $S$ 中拿出最小值 $u$。 若 $b_i>b_{i-1}$ ，则加入 $b_i$ ，并从 $S$ 中拿出最大值 $v$。 根据 $i\leq b_i\leq 2n-i$ 这里能保证总是有 $u<b_i<v$。 - 于是，我们将问题转化为 ： 统计满足下列条件的 $b$ 序列的个数。 - （将序列 $a$ 排序） $b_i\in\{a_i,a_{i+1},...,a_{2n-1}\}$。 - 对于任意的 $j<i$ 都不满足 $b_i<b_j<b_{i+1}$ 或 $b_{i+1}<b_j<b_i$ 考虑 $\rm DP$。 若按照 $b_1\sim b_n$ 的顺序考虑，第二条限制将会难以处理。不妨以 $b_n\sim b_1$ 的顺序考虑。 对于 $\{b_i,b_{i+1},...,b_n\}$ ，他们对 $\{b_1,b_2,...,b_{i-1}\}$ 产生的约束是 ： 对于每一组 $b_i,b_{i-1}$ ，区间 $(b_i,b_{i-1})$ （或区间 $(b_{i-1},b_i)$）中不能再选择数。 （这些开区间的并集会形成一个中间有些断点的区间） 于是，记 $dp[i][l][r]$ 表示考虑了 $b_{i\sim n}$ ，$b_i$ 左侧还剩 $l$ 个数可选，右侧还剩 $r$ 个数可选的方案数。 转移时，暴力枚举 $b_i$ 即可。复杂度为 $O(n^4)$。 现在考虑 $a$ 中有重复数的情况。若将它们按照出现顺序比较大小，序列的合法判据不变，但序列的等价判据改变。 因此，$l,r$ 要改成 “去重后” 还有 $l$ 或 $r$ 个数， ```cpp #include<algorithm> #include<cstdio> #define MaxN 105 using namespace std; const int mod=1000000007; int n,a[105],cl[105],cr[105] ,dp[55][105][105]; int main() { scanf("%d",&n); for (int i=1;i<=2*n-1;i++)scanf("%d",&a[i]); sort(a+1,a+2*n); for (int i=1;i<=2*n-1;i++) cl[i]=cl[i-1]+(a[i]!=a[i-1]); for (int i=2*n-1;i;i--) cr[i]=cr[i+1]+(a[i]!=a[i+1]); int m=cl[2*n-1]; dp[n][cl[n]][cr[n]]=1; for (int i=n-1;i;i--) for (int l=1;l<=m;l++) for (int r=1;r<=m;r++) if (dp[i+1][l][r]){ int sav=dp[i+1][l][r]; dp[i][l][r]=(dp[i][l][r]+sav)%mod; //左右两侧能选择的最后一个数，一定都是 b(i+1) 本身。若选择，则不会产生新的断点。 for (int k=cl[i];k<l;k++) dp[i][k][r+1]=(dp[i][k][r+1]+sav)%mod; //若选择一个靠左的 bi , 则会给 r 增加一个漏洞 for (int k=cr[2*n-i];k<r;k++) dp[i][l+1][k]=(dp[i][l+1][k]+sav)%mod; //若选择一个靠右的 bi , 则会给 l 增加一个漏洞 } int ans=0; for (int l=1;l<=m;l++) for (int r=1;r<=m;r++) ans=(ans+dp[1][l][r])%mod; printf("%d",ans); return 0; } ```