一类基于笛卡尔树的排列计数DP

command_block · 2021-10-21 22:00:06 · 个人记录

P5999 [CEOI2016]kangaroo

题意 ： 有 n 个草丛排成一排，编号 1\sim n 。

有一只袋鼠，从 s 出发，每次跳一步跳到一个其他的草丛，经过每个草丛恰好一次，最终到达 t。显然他会跳跃 n-1 次。

为了不被人类发现，袋鼠每次跳跃的方向必须与前一次不同。

求方案数模 10^9+7 的结果。

• 可以合并两段。

  此时 i 比已有的任一个数都要大，必然可以合成并作为波峰。

  f_{i,j-1}\leftarrow (j-1)\times f_{i-1,j}

• 当 i=s 时

  • 作为新的一段插在最前面 ：f_{i,j+1}\leftarrow f_{i-1,j}

  • 放在最前面的段的前面 ：f_{i,j}\leftarrow f_{i-1,j}

  （i=t 时类似）

可以发现，每种合法的排列都恰会被计数一次。

首先显然被计数的排列都是合法的，只需证每种合法排列恰只有一种计数方式。

对于给定的合法排列 P ，从小到大考虑其中元素，维护两侧为波谷的连续段，每次插入可以得到对应的操作。

不难发现这类似于水淹笛卡尔树并维护森林，不同排列对应不同的笛卡尔树，自然，水淹森林的过程也就不同。

复杂度 O(n^2)。

#include<algorithm>
#include<cstdio>
#define MaxN 2050
using namespace std;
const int mod=1000000007;
int n,s,t,f[MaxN][MaxN];
int main()
{
  scanf("%d%d%d",&n,&s,&t);
  f[0][0]=1;
  for (int i=1;i<=n;i++)
    if (i==s||i==t){
      for (int j=1;j<=i;j++)
        f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
    }else {
      int c=(i>s)+(i>t);
      for (int j=1;j<=i;j++)
        f[i][j]=(1ll*j*f[i-1][j+1]+1ll*(j-c)*f[i-1][j-1])%mod;
    }
  printf("%d",f[n][1]);
  return 0;
}

CF704B Ant Man

题意 ： 有 n 个元素，第 i 个元素有五个参数x_i,a_i,b_i,c_i,d_i。

• 求出一个 1 \sim n 的排列 P，满足 P_1 = s, P_n = e，同时最小化这个排列的权值。

• 排列 P 的权值为 \sum_{i=1}^{n-1} f(P_i, P_{i+1})，其中 f(i,j) 的值有两种情况：

  • 若 i>j，则 f(i,j) = x_i - x_j + c_i + b_j。
  • 若 i<j，则 f(i,j) = x_j - x_i + d_i + a_j。

• 两侧都比自己大：自成一段。注意若 i>s,e，j=1 则无法转移，此时找不到空位加入新的段。

  f_{i,j+1}\leftarrow f_{i-1,j}+b_i+d_i

• 两侧都比自己小：合并两段。

  f_{i,j-1}\leftarrow f_{i-1,j}+a_i+c_i

• 左小右大：贴在一段右侧。注意若 i>e,j=1 则无法转移。

  f_{i,j-1}\leftarrow f_{i-1,j}+a_i+d_i

• 左大右小：贴在一段左侧。注意若 i>s,j=1 则无法转移。

  f_{i,j-1}\leftarrow f_{i-1,j}+b_i+c_i

• i=s$ 或 $i=e

  就只需考虑贴最左侧和贴最右侧的情况，和上面类似。

复杂度 O(n^2) 。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 5050
using namespace std;
const ll INF=1ll<<60;
#define chkmin(a,b) a=min(a,b)
int n,s,e,x[MaxN],a[MaxN],b[MaxN],c[MaxN],d[MaxN];
ll f[2][MaxN];
int main()
{
  scanf("%d%d%d",&n,&s,&e);
  for (int i=1;i<=n;i++)scanf("%d",&x[i]);
  for (int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]+=x[i];}
  for (int i=1;i<=n;i++){scanf("%d",&b[i]);b[i]-=x[i];}
  for (int i=1;i<=n;i++){scanf("%d",&c[i]);c[i]+=x[i];}
  for (int i=1;i<=n;i++){scanf("%d",&d[i]);d[i]-=x[i];}
  for (int i=1;i<=n;i++)f[01][i]=INF;
  for (int i=1,cur=0;i<=n;i++){
    cur^=1;
    for (int j=0;j<=i;j++)f[cur][j]=INF;
    if (i!=s&&i!=e){
      for (int j=0;j<i;j++){
        if (i<max(s,e)||j>1)chkmin(f[cur][j+1],f[cur^1][j]+b[i]+d[i]);
        if (j>1)chkmin(f[cur][j-1],f[cur^1][j]+a[i]+c[i]);
        if ((i<e||j>1)&&j>0)chkmin(f[cur][j],f[cur^1][j]+a[i]+d[i]);
        if ((i<s||j>1)&&j>0)chkmin(f[cur][j],f[cur^1][j]+b[i]+c[i]);
      }
    }else if (i==s){
      for (int j=0;j<i;j++){
        chkmin(f[cur][j+1],f[cur^1][j]+d[i]);
        if (j>0)chkmin(f[cur][j],f[cur^1][j]+c[i]);
      }
    }else if (i==e){
      for (int j=0;j<i;j++){
        chkmin(f[cur][j+1],f[cur^1][j]+b[i]);
        if (j>0)chkmin(f[cur][j],f[cur^1][j]+a[i]);
      }
    }
  }printf("%lld",f[n&1][1]);
  return 0;
}

Loj#2743. 「JOI Open 2016」摩天大楼

题意 对于 A_{1\sim n} 的排列 P ，定义其“波动度”为：

求波动度 \leq c 的排列数目。答案对 10^9+7 取模。

• 合并两段 ：

  • 两侧紧贴：不合法，这样早就会触发自动开机。

  • 一侧紧贴，另一侧空一位自动开机： f_{i,j}\times 2(j-1)\rightarrow f_{i+2,j-1}

  • 两侧各空一位自动开机： f_{i,j}\times (j-1)\rightarrow f_{i+3,j-1}

• 贴在某段一侧 ：

  • 紧贴： f_{i,j}\times 2j\rightarrow f_{i+1,j}

  • 空一位自动开机： f_{i,j}\times 2j\rightarrow f_{i+2,j}

最终 f_{n,1} 是答案。

复杂度 O(n^2)。

#include<algorithm>
#include<cstdio>
#define MaxN 405
using namespace std;
#define add(a,b) a=(a+b)%mod
int n,mod,a[MaxN],f[MaxN][MaxN];
int main()
{
  scanf("%d%d",&n,&mod);
  f[0][0]=1;
  for (int i=0;i<n;i++){
    for (int j=0;j<=i;j++){
      add(f[i+1][j+1],1ll*f[i][j]*(j+1));
      if (j>=2){
        add(f[i+2][j-1],1ll*f[i][j]*2*(j-1));
        add(f[i+3][j-1],1ll*f[i][j]*(j-1));
      }
      if (j>=1){
        add(f[i+1][j],1ll*f[i][j]*2*j);
        add(f[i+2][j],1ll*f[i][j]*2*j);
      }
    }
  }printf("%d",f[n][1]);
  return 0;
}