自动搬运

查看原文

来自洛谷，原作者为

	DreamLand_zcb 此生无悔入MC，来世还做方块人！

搬运于2025-08-24 22:41:34，当前版本为作者最后更新于2023-10-08 22:46:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

题目传送门

思路

设状态 $dp[i][j]$ 其中 $i$ 表示前 $i$ 个数中，有 $j$ 个折点的方案数。

考虑状态转移，显然 $dp[i][j]$ 只能影响到 $dp[i+1][j]$、$dp[i+1][j+1]$、$dp[i+1][j+2]$，证明如下：

首先需要确定，在原序列中插入第 $i + 1$ 个数，这个 $i + 1$ 是所有数中最大的，所以只要在非头/尾部插入这个点，这个点一定就是新的折点。

1. $dp[i+1][j]$ 表示插入第 $i + 1$ 个点后没有新增折点：

   例：

   情况一如图，当 $i + 1$ 插入波峰 $x$ 左右侧时，$x$ 不再是折点，折点变成了 $i + 1$，此时折点数不变。

   

   情况二如图，当 $i + 1$ 插入序列头尾 $x$ 左右时，$x$ 依然不是折点，序列没有新增折点，此时折点数不变（如果头或尾的点是向下走的那么插入后新增了一个点，不属于该范围，此时只有在其中一边插入 $i + 1$ 才能满足不增加新折点）。

   总结一下，当 $j$ 为奇数，总共 $\dfrac {j-1}2 \times 2 + 2 = j + 1$ 种可能。当 $j$ 为偶数，总共 $\dfrac {j}2 \times 2 + 1 = j + 1$ 中可能，所以转移方程：

   $$dp[i+1][j] = dp[i][j] \times (j + 1)$$

2. $dp[i+1][j+1]$ 表示插入第 $i + 1$ 个点后新增了一个转折点。

   只有一种情况，即当在序列头和尾向下走时在头和尾前后插入 $i + 1$ 只增加一个转折点，如图，$x$ 为新增的一个转折点。

   

   所以转移方程：

   $$dp[i+1][j+1] = dp[i][j] \times 2$$

3. $dp[i+1][j+2]$ 表示插入第 $i + 1$ 个点后新增了两个转折点。

   显然在除了以上所有情况，其他地方插入 $i + 1$ 都会新增两个折点，转移方程：

   $$dp[i+1][j+2] = dp[i][j] \times (i + 1 - (j + 1) - 2) $$$$= dp[i][j] \times (i - j - 2)$$

初始值：$dp[1][0] = 1$、$dp[i][0] = 2 (1 < i < n)$。

答案：$dp[n][k-1]$。

代码

#include <bits/stdc++.h>
#define ll long long
#define setp setprecision
#define mem(a, m) memset(a, m, sizeof(a))
using namespace std;

const int MOD = 123456;
int n, k;
int dp[505][505];
int mod(int a)
{
	return a % MOD;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	dp[1][0] = 1;
	for(int i=2;i<n;i++)
	{
		dp[i][0] = 2;
		for(int j=0;j<=i;j++)
		{
			dp[i+1][j] += mod(dp[i][j] * (j + 1));
			dp[i+1][j+1] += mod(dp[i][j] * 2);
			dp[i+1][j+2] += mod(dp[i][j] * (i - j - 2));
		}
	}
	cout << dp[n][k-1] % MOD;
	return 0;
}