蓝桥-排列数

题目

https://www.lanqiao.cn/problems/240/learning/

方法一：暴力

from itertools import permutations

n, k = map(int, input().split())

a = [i for i in range(1, n + 1)]
ans = 0
for num in permutations(a):
    tmp = 0
    for i in range(1, n-1):
        if num[i - 1] < num[i] and num[i + 1] < num[i] or \
                num[i - 1] > num[i] and num[i + 1] > num[i]:
            tmp += 1
    if tmp + 1 == k:
        ans += 1
print(ans)

方法二：DP

思路：

参考一下这篇文章，主要是它图，然后用我的理解重新说一下。

首先是状态的定义。dp[i][j]表示取1~i的数组成的j单调序列的数量。j单调序列，也就是说这个序列中有j个单调的区间，j-1个折点，

现在考虑将i插入到1~i-1的排列中折点的数量变化情况。

假设现在这个序列是j单调序列，最后结论是：

对于第1个区间，
1. 如果是单调增，在最前面插入，折点数加1；
2. 如果是单调减，在最前面插入，折点数不变，在第1个和第2个数之间插入，折点数加1；
对于最后1个区间，
1. 如果是单调增，在最后面插入，折点数不变，在最后1个和倒数第2个之间插入，折点数加1；
2. 如果是单调减，在最后面插入，折点数加1；
在波峰这个点的两边插入，折点数不变；
在其他位置插入，折点数加2。

发现折点最多增加2个。i插入的位置按折点变化情况分类：

折点数不变
1. 波峰这个点的两边
2. 第一个区间如果单调减的最前面
3. 最后一个区间如果单调增的最后面
其实，可以更加总结成：单调增区间的最后面或单调减区间的最前面。这里的区间的两端是波峰或波谷或整个序列的两端。这样的话，每个区间都能有一个位置让i插入后使得折点数不变，数量为区间个数j;
折点数加1
1. 第1个区间如果单调增，插在最前面，如果单调减，插在第1个和第2个数之间
2. 最后1个区间如果单调增,插在最后两个数之间，如果单调减，插在最后面
也就是说，不管单调的方向，整个序列中总有2个位置使得折点数加1；
折点数加2

其余位置。因为i-1的排列一共有i个位置可以插入，前面用了`j+2

提醒的是:

要插入的i是比现有序列的所有数都大的。
i-1个数一共有i个可以插入的地方。
j单调序列，也就是说这个序列中有j个单调的区间，j-1个折点，

所以，dp[i][j]是将i插入到i-1的排列中后折点数为j-1，所以dp[i]][j]是由dp[i-1][j]、dp[i-1][j-1]和dp[i-1][j-2]转移过来：

dp[i-1][j]，将i插入i-1的排列后折点数不变，数量有j个；
dp[i-1][j-1]，将i插入i-1的排列后折点数加1，数量有2个；
dp[i-1][j-2]，将i插入i-1的排列后折点数加2，这里的区间个数为j-2，一共有i个位置各异插入，去掉不变和加1两种情况的j-2和2个，所以有i-j个。

所以状态转移方程为：dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*2+dp[i-1][j-2]*(i-j)。

初始状态：dp[2][1] = 2，也就是两个数的两种排列情况。很多地方有dp[1][1] = 1，我觉得无所谓。

代码

n, k = map(int, input().split())

dp = [[0] * (k + 1) for _ in range(n + 1)]
# dp[1][1] = 1
dp[2][1] = 2
for i in range(3, n + 1):
    for j in range(1, k + 1):
        dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1] * 2 + (dp[i - 1][j - 2] * (i - j) if j > 1 else 0)

print(dp[n][k] % 123456)

一点坑：

因为j循环里和上一行j之后的没有关系，所以我将dp设置成了(n+1)*(k+1)的大小，这个时候就必须要判断一下j-2是否大于0，不然回事负数仍然会有值。