本题涉及到卡特兰数,先用一个例题说说卡特兰数是什么东西:
回到当前问题,本题中push可以看作0,pop可以看作1,即push的操作不少于pop的操作,即卡特兰数问题。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 40;
int n;
LL C[N][N]; //组合数c[i][j]表示从i个数中选j个数
int main()
{
for (int i = 0; i < N; i ++ ) //题目n较小,所以用递推法求组合数
for (int j = 0; j <= i; j ++ )
if (!j) C[i][j] = 1;
else C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; //组合数递推公式
cin >> n;
cout << C[n * 2][n] / (n + 1) << endl; //卡特兰数公式
return 0;
}