codevs 1086_栈_dp

发布于 2019-05-13  7 次阅读


题目描述

将对给定的n,计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。


思路

出栈方式其实就是一个卡特兰数,用dp公式推就可以了
f[i]表示深度为i的栈出栈方式数
f[i]=f[i-1]*(4*i-2)/(i+1)
O(n)


#include 
int main()
{
    int n;
    long long ans=1;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        ans=ans*(4*i-2)/(i+1);
    printf("%lld\n",ans);
}
]]>