题解 P1044 【栈】

# 主要原理：卡特兰数 首先，根据题意，自己枚举了一些比较小的时候的结果，感觉很熟悉，突然发现—— > 这不就是卡特兰数吗？！ 紧接着我~~企图~~上[百度百科](https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdin)找到~~题解~~卡特兰数数列，用于打表输出。 这是~~被我打了的~~表： ``` const long long catalan[] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452}; ``` 综合题意，得程序： ``` #include <iostream> using namespace std; const long long catalan[] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452}; int main() { int n; cin>>n; cout<<catalan[n]<<endl; return 0; } ``` 打表数据出处：https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdin#1