luogu P5999 [CEOI2016]kangaroo

https://www.luogu.com.cn/problem/P5999

NB题

妙妙DP题

直接考虑$S$出发$T$结束并不是很好做，

经典套路，转换成插入型DP

考虑$DP$路线，分成若干段，然后再拼起来

$f[i][j]$表示考虑前$i$个数，分成了$j$段，注意到一个大的可以把两个小的拼起来
从小到大插入

$f[i][j]=f[i-1][j-1]\ast j+f[i-1][j+1]\ast j$即单独成一段插在空隙里或者把两段合并

$S$和$T$单独处理就行了

具体细节看代码吧

code:

#include<bits/stdc++.h>
#define N 2005
#define mod 1000000007
using namespace std;
int f[N][N], n, s, t;
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] = (1ll * (j - (i >= s) - (i >= t)) * f[i - 1][j - 1] % mod + 1ll * j * f[i - 1][j + 1] % mod) % mod;
            } else {
                f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
            }
        }
    printf("%d", f[n][1]);
    return 0;
}