【题解】火车进出站问题
题目链接
解题思路
递推
我们可以递推,枚举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/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者