[DP记录]AT2366 [AGC012F] Prefix Median

· · 个人记录

题意 ： 给定一个长为 2n-1 的序列 a ，定义中位数序列 b={\rm midsq}(a) 如下 ：

给出序列 a ，可以将其任意打乱，问能产生多少个本质不同的 {\rm midsq}(a)。

答案对 10^9+7 取模。

------------ 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 个数，

#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;
}