由 SDOI 2010 想到的另一个做法。

这里先定义几个名词：

在一个排列中，一个山峰是指排列中的一个元素同时大于两边的元素。

在一个排列中，一个山谷是指排列中的一个元素同时小于两边的元素。

那么题目中的折点数量即为排列中山谷数量和山峰数量的和。

算法1 $\ 60 pts$

($\text{DP}$) $O(n ^ 3 k)$

从暴力 $\text{DP}$ 开始，暂时先忽略数据范围。

将最后一个折点拆成山峰和山谷分别考虑。

设 f[i][j][k][0 / 1] 表示填了前 i 个数，其中最后一个数的排名为 j，且该排列为 k 单调序列，且最后两个数递减/递增的方案数。

推状态转移方程，考虑填最后一个数。

不难发现，直接推状态转移方程，会发生冲突，因为 j 可能在 1 ~ i - 1 中已经被填过了。

考虑把 1 ~ i - 1 的排列中，所有 $\geq j$ 的数都 $+1$，然后将 j 填入。

考虑从 f[i - 1][r][k][0 / 1] 进行转移，将 r 分成以下几种情况：

1. 如果 $r < j$
   那么我们将 j 填入该排列后，最后两个数递增。再考虑原排列中最后两个数是否递增。
   1. 如果递增，则放入 j 后，折点数不增加，那么有 f[i][j][k][1] += f[i - 1][r][k][1]
   2. 如果递减，则放入 j 后，折点数增加，那么有 f[i][j][k][1] += f[i - 1][r][k - 1][0]
2. 如果 $r \geq j$
   那么我们将 j 填入该排列后，最后两个数递减。再考虑原排列中最后两个数是否递增。
   1. 如果递增，则放入 j 后，折点数增加，那么有 f[i][j][k][0] += f[i - 1][r][k - 1][1]
   2. 如果递减，则放入 j 后，折点数不增加，那么有 f[i][j][k][0] += f[i - 1][r][k][0]

最后考虑初始化，我们上面的 [0 / 1] 这一维限制了排列中至少有两个数，所以我们要手推一下排列中只有 $1 / 2$ 个数的情况。

这里直接给出结论：

f[1][1][1][0] = 1;
f[2][1][1][0] = f[2][2][1][1] = 1;

那么我们就完美的解决了这题。

直接做肯定是不行的，状态数量太多了，要开滚动数组。

复杂度

$\text{DP} 时间复杂度 = 状态数量 \times 转移复杂度$

该算法中状态数量为 $2 n ^ 2 k$，转移复杂度为 $O(n)$，故总时间复杂度为 $O(n ^ 3 l)$

空间复杂度 $O(n k)$

C++ 代码

#include <cstdio>
#include <cstring>

const int N = 505;
const int mod = 123456;

int n, m;
int f[2][N][N][2];

int main()
{
    scanf("%d%d", &n, &m);

    f[1][1][1][0] = 1;
    f[0][1][1][0] = f[0][2][1][1] = 1;
    for (int i = 3; i <= n; i ++ )
    {
        memset(f[i & 1], 0, sizeof f[n & 1]);
        for (int j = 1; j <= i; j ++ )
            for (int k = 1; k <= i && k <= m; k ++ )
            {
                for (int r = 1; r <= i; r ++ )
                    if (r < j) (f[i & 1][j][k][1] += f[i - 1 & 1][r][k][1] + f[i - 1 & 1][r][k - 1][0]) %= mod;
                    else    (f[i & 1][j][k][0] += f[i - 1 & 1][r][k][0] + f[i - 1 & 1][r][k - 1][1]) %= mod;
            }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        (res += f[n & 1][i][m][0] + f[n & 1][i][m][1]) %= mod;

    printf("%d\n", res);

    return 0;
}

算法2 $\ 100 pts$

($\text{DP}$) $O(n ^ 3)$

状态数量不是很好优化，考虑从转移复杂度上进行优化。（一般的 $\text{DP}$ 优化都是这么考虑的）

不难发现，我们枚举 $r$ 的那一维，可以用前缀和优化掉。

记 $\begin {aligned} s(i, l, r, k, w) = \sum _ {j = l} ^ r f[i][j][k][w] \end {aligned}$

那么我们可以用 $s$ 优化转移：

f[i][j][k][1] += s(i - 1, 0, j - 1, k, 1) + s(i - 1, 0, j - 1, k - 1, 0)
f[i][j][k][0] += s(i - 1, j, i - 1, k, 0) + s(i - 1, j, i - 1, k - 1, 1)

其中 $s$ 函数用前缀和实现。

复杂度

该算法中状态数量为 $2 n ^ 2 k$，转移复杂度为 $O(1)$，所以总时间复杂度为 $O(n ^ 2 k)$

空间复杂度 $O(n k)$

C++ 代码

#include <cstdio>
#include <cstring>

const int N = 505;
const int mod = 123456;

int n, m;
int f[2][N][N][2];
int s[2][N][N][2];

int main()
{
    scanf("%d%d", &n, &m);

    f[1][1][1][0] = 1;
    f[0][1][1][0] = f[0][2][1][1] = 1;
    s[0][1][1][0] = s[0][2][1][0] = s[0][2][1][1] = 1;
    for (int i = 3; i <= n; i ++ )
    {
        memset(f[i & 1], 0, sizeof f[0]);
        memset(s[i & 1], 0, sizeof s[0]);
        for (int j = 1; j <= i; j ++ )
            for (int k = 1; k <= i && k <= m; k ++ )
            {
                (f[i & 1][j][k][1] += s[i - 1 & 1][j - 1][k][1] + s[i - 1 & 1][j - 1][k - 1][0]) %= mod;
                (f[i & 1][j][k][0] += s[i - 1 & 1][i - 1][k][0] - s[i - 1 & 1][j - 1][k][0]) %= mod;
                (f[i & 1][j][k][0] += s[i - 1 & 1][i - 1][k - 1][1] - s[i - 1 & 1][j - 1][k - 1][1]) %= mod;
                s[i & 1][j][k][0] = (s[i & 1][j - 1][k][0] + f[i & 1][j][k][0]) % mod;
                s[i & 1][j][k][1] = (s[i & 1][j - 1][k][1] + f[i & 1][j][k][1]) % mod;
            }
    }

    printf("%d\n", ((s[n & 1][n][m][0] + s[n & 1][n][m][1]) % mod + mod) % mod);

    return 0;
}

$$ $$