erp系统十大软件_建设人才网证书查询_竞价推广返点开户_现在有什么技能培训班

题源：P1722 矩阵 II - 洛谷

看了题目之后，需要注意的是：

①在1 ~ i 个格子中红色数量 >= 黑色数量

②最后，在2 * n 个格子中，红色数量 == 黑色数量

根据这两个约束条件，可以知道，第一个格子必须是红色

第一种解法：动态规划

使用组合数学中递推思想

统计方案数目，就是最简单的动态规划。

可以按照下面的方法进行分析：

1. 问题建模

问题描述：
在 2n 个算筹中放置 n 个红色算筹，满足 任意前 i 个算筹中红色算筹数 ≥ ⌈i/2⌉（即红色算筹始终不少于半数）。
DP状态定义：
dp[i][j] 表示前 i 个算筹中放置 j 个红色算筹的合法方案数。

2. 动态规划转移方程

递推关系：
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
- dp[i-1][j]：第 i 个算筹不选红色（即选黑色）。
- dp[i-1][j-1]：第 i 个算筹选红色。
- 在循环里面写着一步的时候就可以加上模 100了。
约束条件：
j ≥ ⌈i/2⌉，确保任意前缀中红色算筹数满足要求。

3. 算法核心逻辑

初始化：
dp[1][1] = 1，表示第一个算筹必须为红色（因为 ⌈1/2⌉ = 1）。
递推填充DP表：
- 外层循环遍历算筹总数 i（从 2 到 2n）。
- 内层循环遍历红色算筹数 j（从 ⌈i/2⌉ 到 i）。
结果输出：
dp[2n][n] 表示 2n 个算筹中放 n 个红色算筹的合法方案数。

AC代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int dp[510][510];
int main()
{int n;cin>>n;dp[1][1] = 1;for(int i = 2;i <= 2 * n;i++){for(int j = 1;j <= i;j++){if(j >= (i + 1) / 2){dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 100;}}}printf("%d",dp[2*n][n]);return 0;}

第二种解法：卡特兰数

卡特兰数是一系列自然数，其第n项的公式为：

其中C0 = 1, C1 = 1, C2 = 2, C3 = 5, C4 = 14, C5 = 42, C6 = 132, C7 = 429....

关于它的一些公式：

有通项公式推出递推公式相对其他数学公式而言较简单，可以自证。

2.卡特兰数代码实现

    f[0] = f[1] = 1;for(int i = 2;i <= n;i++){for(int j = 0;j < i;j++){f[i] += f[j] * f[i - 1 - j]; // 递推公式2}}

3. 为什么这道题可以使用卡特兰数

因为卡特兰数常用场景是：

①出栈次序：假设有一个栈，将数字 1,2,…,n 按顺序依次入栈，允许在任意时刻出栈。求所有可能的 出栈序列 的总数。

②n对括号正确匹配问题：给定 n 对括号（即 n 个左括号 ( 和 n 个右括号 )），求所有 合法匹配的括号序列 的总数。

③给定节点组成二叉搜索树：给定 n 个不同的节点（值唯一），求能组成多少种 结构不同的二叉搜索树（BST）。

所以，我们这道题就可以看成是出栈次序问题。就是求将红色看成是入栈操作，黑色看成是出栈操作。任意前缀（前面格子）中红色 >= 黑色，等价于入栈数 >= 出栈数。这也是出栈序列中的合法性，保证入栈数大于等于出栈数。所以就可以看成是出栈次序问题。

下面讲解出栈次序问题：

①首先，设f(n) 为序列个数中为 n 的出栈序列种数。

②并且假定，从开始到第一次出栈到空为止，这段过程中的第一个出栈序数为 k。

③首次出空之前第一个出栈的序数 k 将 1 ~ n 的序列分为两个序列：第一段序列是 1 ~ k - 1，第二段序列是 k + 1 ~ n.

④现在，把 k 看成是一个确定的序数，根据乘法原理，f(n) 的问题等价于 —— 序列个数为 k - 1 (第一段)的出栈序列数乘以序列个数为 n - k 的出栈序列数（递归思想），即f(n) = f(k -1) * f(n - k);

⑤因为k的范围是 1 ~ n,所以再结合加法原理，将 k 取到不同值得序列种数相加，得到得总序列种数为：f(n)=f(0)f(n−1)+f(1)f(n−2)+……+f(n−1)f(0)。

⑥可以发现，这个公式与卡特兰数得递推式二是一样的。

这道的解为第 n 个卡特兰数。