[CEOI2016] kangaroo

前言

连续段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;
}
上一篇:一次完整的HTML请求[含HTML渲染过程]


下一篇:【YOLO】深度学习-物体检测-YOLO系列(网易云课程笔记)