商务贸易网站建设,公司注册步骤流程,藤虎广州网站建设,首页网站备案号添加题目背景
usqwedf 改编系列题。
题目描述
如果你在百忙之中抽空看题#xff0c;请自动跳到第六行。
众所周知#xff0c;在中国古代算筹中#xff0c;红为正#xff0c;黑为负……
给定一个12n 的矩阵#xff08;usqwedf#xff1a;这不是一个 2n 的队列么#xff…题目背景
usqwedf 改编系列题。
题目描述
如果你在百忙之中抽空看题请自动跳到第六行。
众所周知在中国古代算筹中红为正黑为负……
给定一个1×2n 的矩阵usqwedf这不是一个 2n 的队列么现让你自由地放入红色算筹和黑色算筹使矩阵平衡[即 ∀i∈[1,2n]1∼i 格中红色算筹个数大于等于黑色算筹]。
问有多少种方案满足矩阵平衡注意红色算筹和黑色算筹的数量必须相等。
输入格式
正整数 n。
输出格式
方案数 t 对 100取模后的结果。
输入输出样例
输入
2
输出
2
说明/提示
样例解释 方案一红黑红黑 方案二红红黑黑
数据范围
1≤n≤100
题解一dp
每次放都有两种选择因此我们只需要一种颜色就可以求出答案
递推方程 dp[i][j]dp[i-1][j]dp[i-1][j-1];
代码实现
#includeiostream
using namespace std;
const int N510;
int s[N][N]; //前i个格子里放j个红色球 int main(){int n;cinn;s[1][1]1; //一个格子放一个球只有一种情况 for(int i2;inn;i){for(int j(i1)/2;ji;j){ //红色格子的数必须大于等于总格子数的一半 s[i][j](s[i-1][j]s[i-1][j-1])%100;}}couts[2*n][n]endl;return 0;
}
解法二卡特兰数
#includeiostream
using namespace std;
const int N510;
int s[N];
int main(){int n;cinn;s[0]s[1]1;for(int i2;in;i){for(int j1;ji;j){s[i]s[j-1]*s[i-j];s[i]%100;}}couts[n]endl;return 0;
}
