29 lines
919 B
C++
29 lines
919 B
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
|
||
int n;
|
||
// i 表示队列里还有几个待排的数，
|
||
// j 表示栈里有 j 个数，dfs(i,j)表示此时的情况数
|
||
// 不重不漏的描述了所有情况
|
||
|
||
LL dfs(int i, int j) {
|
||
LL ans = 0;
|
||
//(1)队列空，栈空
|
||
if (i == 0 && j == 0)ans += 1; //这是递归出口，增加一种方法
|
||
//(2)队列空,栈不空
|
||
if (i == 0 && j > 0) ans += 1; //只能一个个蹦出去啦~
|
||
//(3)队列不空,栈空
|
||
if (i > 0 && j == 0) ans += dfs(i - 1, j + 1); //从队列中取一个，放入到栈中
|
||
//(4)队列不空,栈不空
|
||
if (i > 0 && j > 0) ans += dfs(i, j - 1) + dfs(i - 1, j + 1);
|
||
//有两种选择，一是队列不动，栈中出去一个；另一种是队列取一个，放入栈中
|
||
return ans;
|
||
}
|
||
|
||
int main() {
|
||
cin >> n;
|
||
printf("%lld", dfs(n, 0));
|
||
return 0;
|
||
} |