前言
连续段DP练习题，调半天发现变量重名了qwq。
题目
讲解
可以发现题目等价于求一个 \(s\) 开头 \(t\) 结尾的 \(n\) 的一个排列，满足每个数比两边的数都大或者都小。
我们考虑从小到大一个数一个数插进去，每次每个数可以单独成为一个区间或者拼接两个区间。
很自然的设 \(dp_{i,j}\) 表示考虑了前 \(i\) 个数，现在有 \(j\) 个区间。
每个数可以做两种操作：
- 新开一个区间。
- 拼接两个区间。
不难发现由于我们知道区间个数，因此很容易知道每种操作有多少种。
我最开始的思路是一开始就确定 \(s,t\) 怎么放，然后再枚举第一步、最后一步是向前还是向后，最后发现不但非常麻烦，而且不可做，实际上我们只需要特殊处理一下 \(s,t\) 处的转移即可。
具体实现可以看代码，时间复杂度 \(O(n^2)\)。
代码
小知识：滚动数组不但空间小，而且更快。
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 2005;
const int MOD = 1e9+7;
int n,s,t;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int dp[2][MAXN];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); s = Read(); t = Read();
dp[1][1] = 1;
for(int i = 2;i <= n;++ i){
bool now = i&1,lst = now^1;
memset(dp[now],0,sizeof(dp[now]));
for(int j = 1;j <= i;++ j){
if(i == s || i == t){
dp[now][j] = (dp[now][j] + dp[lst][j-1]) % MOD;
dp[now][j] = (dp[now][j] + dp[lst][j]) % MOD;
}
else {
int q = j - (i>s) - (i>t);
if(q > 0) dp[now][j] = (dp[now][j] + 1ll * dp[lst][j-1] * q) % MOD;
dp[now][j] = (dp[now][j] + 1ll * dp[lst][j+1] * j) % MOD;
}
}
}
Put(dp[n&1][1],'\n');
return 0;
}