P1722 矩阵 II 题解

[题目传送门](https://www.luogu.com.cn/problem/P1722) [AC记录](https://www.luogu.com.cn/record/46601861) 这道题其实就是卡特兰数的第n个，但是，我不会。 而我又想到了01背包，让a[i][j]为前i个位置装j个红色，请注意，题目描述有问题 根据样例可得最后结果要求红色和黑色个数一样，所以输出a[n*2][n] 上代码！ 我把空间优化了一下，用的是1维 ```cpp #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; } ```