被学弟吊打了。
第一听到有什么插入型$dp$，没见过，第一次见，写一发。
Solution
首先考虑将坐标排序，每次将一个坐标插入到原数列中。
最终的数列必须满足对于$[2,n-1]$每一个数，要么比周围的都大，要么比周围的都小，由于我们是顺序插入，所以每插入一个数都一定会满足比周围的数都大，先考虑除了$s,t$以外的数。
先考虑分段，具体的，如果我们让一些数的邻居都固定下来了，那么我们显然不能再往它的周围插了，那么它和它的邻居看起来就像一个数一样，我们就让它们成为一段，这样每一次插入的数就只能往段间插入。
考虑如下情况：
- 这个数插在了两个段之间，要合并两段，显然有转移方程式：$f[i][j]+=j\times f[i-1][j+1]$。
- 这个数想单独成段，考虑它与$s$和$t$之间的关系，如果它比$s$大，显然它不能插在队首，如果它比$t$大，显然它不能插在队尾，有转移方程式：$f[i][j]+=(j-(i>s)-(i>t))\times f[i-1][j-1]$。
注意，这些数不能和两端的数合并（合并了会出问题）
为什么不会算重呢，将问题本身看作为每一个点选择邻居的过程，如果它的邻居确定了，自然它的位置就确定了，而如果它的邻居没有固定，那么显然它的现有邻居不会对最终的序列造成影响，因为我们已经强制令它们最后不为邻居了。
然后考虑$s$和$t$的情况：
- 单独成段$f[i][j]+=f[i-1][j-1]$。
- 合并两端$f[i][j] += f[i-1][j-1]$。
而为什么这两个数又可以合并两端呢，因为这两个数已经被强制确定为起点和终点，它们可以合并的邻居一定是在前面插入的，而这样的邻居的邻居肯定也是比邻居更大的（所以上面才不能合并两端），所以是符合要求的。
真妙啊。
这样的形式其实有点类似笛卡尔树。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0;
bool flag = 0;
char c = getchar();
while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
if (res < 0) putchar('-'), res = -res;
if (res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 2005, mod = 1e9 + 7;
int n, s, t;
int f[N][N];
int main()
{
read(n, s, t);
f[1][1] = 1;
for(int i = 2;i <= n;i ++)
for(int j = 1, res;j <= i;j ++)
if(i != s && i != t)
{
res = (i > s) + (i > t);
if(j > res) f[i][j] = (f[i][j] + 1ll * (j - res) * f[i - 1][j - 1] % mod) % mod;
f[i][j] = (f[i][j] + 1ll * j * f[i - 1][j + 1]) % mod;
}
else f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
write(f[n][1]);
return 0;
}
|