题目链接

解题思路

递推

我们可以递推，枚举1在每一个位置的可能，于是整个数列就被划分成了两部分，然后再在两部分中继续递推，时间复杂度为 $O(n^2)$

$$ S_n=\sum^{N}_{k=1}S_{k-1}*S_{N-k} $$

DP

以 Fi 代表有i个数尚未进栈，当前栈中有j个数。会得到DP方程：

$$ F[i][j]=max(F[i-1][j+1],F[i][j-1]); $$

时间复杂度为O(n^2)

数学

由于以上方法都是O(n^2)，而数据范围为6e4，所以明显不可行。我们需要想一个更加快速的数学公式求答案。

于是我们会发现，对于第n次出栈，都必须在前面有n次进展，即设进栈为1，出栈为0，则需满足对于每一个位置，1的前缀和要比0的前缀和大。我们发现这种性质正好满足一个数列：卡特兰数

卡特兰数的推导请自行看蓝书，其公式为 $Cat_n=\frac{C^n_{2n}}{n+1}$

但是这道题如果直接这样高精度做可能还是会爆炸，我们需要用每一个a存储8位可保证空间复杂度。先将其分解然后再相乘可以抵消掉不少相同的数，可以减少时间复杂度。

#include<bits/stdc++.h>
using namespace std;
const long long Mod=1e9;
long long sum[120005];
long long a[120005];
long long tot=1;
void prime(int num,int op){
    int kk=sqrt(num)+1;
    for(int i=2;i<=kk;i++){ 
        if(num==1)return ;
        while(num%i==0){
            sum[i]+=op;
            num/=i;
        }
    }
    if(num>0)sum[num]+=op;
    return ;
}
void mul(long long sum){
    for(int i=1;i<=tot;i++){
        a[i]*=sum;
    }
    for(int i=1;i<=tot;i++){
        a[i+1]+=a[i]/Mod,a[i]%=Mod;
    }
    if(a[tot+1]>0)tot++;
}
int main(){
    int n;
    scanf("%d",&n);
    a[1]=1,tot=1;
    for(int i=n+1;i<=2*n;i++)prime(i,1);
    for(int i=1;i<=n+1;i++)prime(i,-1);
    for(int i=2;i<=2*n;i++){
        for(long long j=1;j<=sum[i];j++){
            mul(i);
        }
    }
    printf("%lld",a[tot]);
    for(int i=tot-1;i>=1;i--)printf("%09lld",a[i]);
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/704/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者