题面
【问题描述】
在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素， 或者同时大于两边的元素。
对于一个 1 ∼ n 的排列，如果可以将这个排列中包含 t 个折点，则它称为 一个 t + 1 单调序列。
例如，排列 (1, 4, 2, 3) 是一个 3 单调序列，其中 4 和 2 都是折点。
给定 n 和 k，请问 1 ∼ n 的所有排列中有多少个 k 单调队列？
【输入格式】
输入一行包含两个整数 n, k。
【输出格式】
输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列 数量除以 123456 的余数即可。
【样例输入】
4 2
【样例输出】
12
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ k ≤ n ≤ 10；
对于 40% 的评测用例，1 ≤ k ≤ n ≤ 20；
对于 60% 的评测用例，1 ≤ k ≤ n ≤ 100；
对于所有评测用例，1 ≤ k ≤ n ≤ 500。
思路
1. 暴力骗分
全排列，再检测是否满足 k-1 个折点的情况，只能过 20 % 的样例。
2. 动态规划
传送门 排列数。
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 505, MOD = 123456;
int f[2][N][N][2], s[2][N][N][2], n, m;
int main() {
while (cin >> n >> m) {
memset(f, 0, sizeof f);
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] = (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] = (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] = (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;
}
}
}
cout << ((s[n & 1][n][m][0] + s[n & 1][n][m][1]) % MOD + MOD) % MOD << endl;
}
return 0;
}
| 标题： | 2019第十届蓝桥杯国赛-G排列数 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/118 |
| 更新： | 2022-09-18 22:40:24 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |