P5999 [CEOI2016] kangaroo

可能（？）有用的 DP trick。

题目链接

先转化题意，我们实际上需要求的就是满足以下条件的 $1\to n$ 排列 $a$ 的个数：

1.$a_1=s,a_n=t$；

2.$\forall i\in [2,n-1],(a_i-a_{i-1})\times (a_i-a_{i+1}) >0$。

如何 DP 呢？这似乎并不好弄，因为我们进行传统的 DP 时我们并不好知道用了哪些数。

于是我们考虑新的思路，尝试分段型 DP。从小到大考虑将每个数插到满足条件的两段之间。这样得到的新段一定是满足条件的，并且不会算重。于是设计状态 $f_{i,j}$ 表示插入了 $i$ 个数，形成了 $j$ 个连续的段的方案数。转移时考虑将 $i$ 插进前面两段之间，或者新建一段就可以了。注意只能将 $s$ 插到最前面，将 $t$ 插到最后面。并且新建一段时不可以将其他数插在 $s$ 之前 $t$ 之后。

或者换一种理解方式，我们将 $f_{i,j}$ 表示使用前 $i$ 个数建了 $j$ 个笛卡尔树。每次转移时，将已有的某两颗笛卡尔树接在当前的 $i$ 上，或者以 $i$ 再建一颗笛卡尔树。容易发现这样构成的笛卡尔树所对应的序列就是满足条件的排列 $a$。

我们这里是将每一段看做相对有序的。其实也可以看成相对无序的，转移方程有所不同。但结果都一样是 $f_{n,1}$。

Code

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=2e3+10,mod=1e9+7;
int n,s,t;
ll f[N][N];
int main()
{
    scanf("%d%d%d",&n,&s,&t);
    f[1][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            if(i!=s&&i!=t)
                f[i][j]=(f[i][j]+f[i-1][j+1]*j+f[i-1][j-1]*(j-(i>s)-(i>t)))%mod;//插到中间或新建一段
            else f[i][j]=(f[i][j]+f[i-1][j]+f[i-1][j-1])%mod;//插到两端或新建一段
        }
    printf("%lld\n",f[n][1]);
    return 0;
}