题解：P1044 [NOIP 2003 普及组] 栈

思路

假设我们用一个函数

\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，转移方程是：

f_{x,y}=f_{x-1,y+1}+f_{x,y-1}

Code

CPP

#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];
}

有问题请指出！

感谢 NJYgocrazy指出一个小错误。

题解：P1044 [NOIP 2003 普及组] 栈

文章操作

思路

Code

相关推荐

评论

题解：P1044 [NOIP 2003 普及组] 栈