自动搬运

查看原文

来自洛谷，原作者为

	CJY 小升初蒟蒻||/article/ugxlm066/team/87748||没有一根棒棒糖解决不了的事情，如果有，就再来一根||最后在线时间：2025年8月24日20时21分

搬运于2025-08-24 21:20:16，当前版本为作者最后更新于2025-03-22 10:51:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

假设我们用一个函数 $\operatorname{C}(x,y)$ 表示：

• $x$：当前还未入栈的数字个数。
• $y$：当前栈中的数字个数。

我们的目标是计算 $\operatorname{C}(n,0)$，即从 $n$ 个数字开始，生成输出序列的方式。

在任何状态下，我们有两种选择：

• push 操作：如果还有数字可以入栈（即 $x>0$），我们可以将一个数字从输入序列中移入栈中。这会减少未入栈的数字个数 $x$，同时增加栈中的数字个数 $y$。因此，该操作对应于 $\operatorname{C}(x-1,y+1)$。
• pop 操作：如果栈中有数字可以出栈（即 $y>0$），我们可以将栈顶数字移出到输出序列中。这不会改变未入栈的数字个数 $x$，但会减少栈中的数字个数 $y$。因此，该操作对应于 $\operatorname{C}(x,y-1)$。

递归的边界条件是：当 $x=0 \land y=n$ 时，表示所有数字已成功输出为一个序列，这算作一种有效方式，返回 $1$；其他不合法状态（如 $x<0 \lor y>n$）返回 $0$。

递归太慢，所以我们可以用 DP，转移方程是：

Code

#include<bits/stdc++.h>
using namespace std;
int f[20][20],n;
int main(){
	cin>>n;
	for(int x=0;x<=n;x++){
		for(int y=0;y<=n;y++){
			if(!x) f[x][y]=1;
			else if(!y) f[x][y]=f[x-1][y+1];
			else f[x][y]=f[x-1][y+1]+f[x][y-1];
		}
	}
	cout<<f[n][0];
}

有问题请指出！

感谢