P1722 矩阵 II 题解

小邱 · 2021-02-15 15:55:29 · 个人记录

题目传送门

AC记录

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

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

根据样例可得最后结果要求红色和黑色个数一样，所以输出a[n*2][n]

上代码！

我把空间优化了一下，用的是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;
}