[CEOI2016] kangaroo（排列dp）

problem

luogu-P5999

solution

每个点只能跳一次，显然跳出来形成的顺序是一个排列。不难联想到最近刷的排列 $dp$。

然后，我觉得难点在于怎么转化这个跳的规则，因为现在并不确定能否按排列 $dp$ 一样分段做。

跳的顺序形成的排列必须满足以下两个条件之一：

• 排列中第 $i$ 个元素必须小于两边的元素。
• 排列中第 $i$ 个元素必须大于两边的元素。

排列的起终点(墙)为 $s,t$。

转化后发现，这是可以排列 $dp$ 的。

我们从小到大考虑 $i$。设 $f(i,j):$ 前 $i$ 个数将排列分成了 $j$ 段的合法方案数。

• $i$ 不是墙。

  • 合并两段，$j$ 段有 $j-1$ 个空。$f(i,j)\leftarrow f(i-1,j+1)\ast j$。

  • 新插一段，可以插在任何位置，但若 $s$ 已过则不能插首，若 $t$ 已过则不能插尾。

    $f(i,j)\leftarrow f(i-1,j-1)\ast (j-(i>s)-(i>t))$。

• $i$ 是墙。只能放在首尾。

  • 单独成段。$f(i,j)\leftarrow f(i-1,j-1)$。
  • 与相邻段合并，相当于延伸。$f(i,j)\leftarrow f(i-1,j)$。

时间复杂度 $O(n^2)$。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define maxn 2005
int f[maxn][maxn];
int n, s, t;

signed main() {
	scanf( "%lld %lld %lld", &n, &s, &t );
	f[1][1] = 1;
	for( int i = 2;i <= n;i ++ )
		if( i ^ s and i ^ t )
			for( int j = 1;j <= n;j ++ )
				f[i][j] = (f[i - 1][j - 1] * (j - (i > s) - (i > t) ) + f[i - 1][j + 1] * j) % mod;
		else
			for( int j = 1;j <= n;j ++ )
				f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;		
	printf( "%lld\n", f[n][1] );
	return 0;
}