P1722 矩阵 II 题解

P1722 矩阵 II 题解

黄衣哥
2022-01-19 / 0 评论 / 31 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月28日,已超过61天没有更新,若内容或图片失效,请留言反馈。

题目传送门

AC记录

这道题其实就是卡特兰数的第n个,但是,我不会。

而我又想到了01背包,让ai为前i个位置装j个红色,请注意,题目描述有问题

根据样例可得最后结果要求红色和黑色个数一样,所以输出an*2

上代码!

我把空间优化了一下,用的是1维

#include<bits/stdc++.h>
using namespace std;
int a[205]; 
int main()
{
    int n,m,i,j;
    scanf("%d",&n);
    for(i=2,a[0]=1;i<=n*2;i++)//i表示第几个位置,第1个位置肯定是红,所以跳过
    {
        for(j=i,m=(i+1)>>1;j>=m;j--)//j从i开始,表示要装j个红色,注意到i/2向上取整,因为红色要>=黑色
        {
            a[j]=(a[j-1]+a[j])%100;//可以是上一次本来就到j个了,或者上一次到j-1了,这次只需要加一个红色就好了,所以两者相加
        }
    }
    printf("%d",a[n]);
    return 0;
}
0

评论 (0)

取消