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

__CJY__ · 2025-03-22 10:51:47 · 题解

思路

假设我们用一个函数 \operatorname{C}(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

#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 指出一个小错误。