[小清新] [dp] P5999 kangaroo

_Cheems · 2023-12-06 14:09:39 · 个人记录

题意

求出满足如下条件的 n 排列：

1. 起点为 s，终点为 t。
2. 对于每个元素 a_i，都有 a_i>{a_{i-1},a_{i+1}} 或 a_i<{a_{i-1},a_{i+1}}。

   思路

   条件 2 很难满足，那么考虑围绕它来做：考虑从小到大插入元素，这样 i 插入到任意位置都是可以的，至少目前时这样的。

然后发现对于任意排列，都能每次找到最大的元素然后以它为中心把排列拆为两部分，不妨逆着做：把序列当成若干个连通块，每个连通块内部满足条件，那么 i 就可以连接相邻连通块。在保证 i 递增的情况下，这样肯定不会计重。

于是定义 f_{i,j} 表示前 i 个元素分为 j 个连通块的方案数。

事实上，对于“插入型 \rm dp”，要考虑的操作有：在块内插入元素、连接两个块、新增块。我们已经解决后两种操作，剩下第一种操作。

仔细想想，对于任意插入操作，都能被转化为后两种操作，于是舍去即可。

但是存在特殊情况不可转化：在最左边的块的左侧和最右边的块的右侧，只需特殊处理下就好。对于此题而言，分别对应的是 i=s,t。

有些细节，具体见代码。

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ADD(a, b) (a) = ((a) + (b)) % mod
const int N = 2e3 + 5, mod = 1e9 + 7;
int n, s, t, f[N][N]; 

signed main(){
    cin >> n >> s >> t;
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            if(i == s || i == t)
                ADD(f[i][j], f[i - 1][j] + f[i - 1][j - 1]);
            else
                ADD(f[i][j], f[i - 1][j + 1] * j + f[i - 1][j - 1] * (j - (i > s) - (i > t)));
                //注意有时头和尾不能放 
    cout << f[n][1];
    return 0;
}