题解 P1044 【栈】
xiejinhao
2019-05-01 00:25:06
# P1044 栈 题解
### 这题运用了大量数论，但我不太想写卡特兰，于是有了这篇题解
#### 虽然说不是卡特兰，貌似都差不多，于是我给出4种做法
1、**递归/记忆化搜索**
------------
看这个数据，我总感觉dfs会超时，~~然后真的超了？（没试过）~~，于是很自然的，我们就会想到记忆化搜索，这也是做这题的一种技巧吧，但无论如何，这也是最基础的
- 下面谈谈搜索(递归)思路：
1. 既然记忆化搜索了，定义一个二维数组$f[i,j]$，用下标 $i$ 表示队列里还有几个待排的数，$j$ 表示栈里有 $j$ 个数，$f[i,j]$表示此时的情况数
1. 那么，更加自然的，只要$f[i,j]$有值就直接返回；
1. 然后递归如何实现呢？首先，可以想到，要是数全在栈里了，就只剩1种情况了，所以：$i=0$时，返回$1$；
1. 然后，有两种情况：一种栈空，一种栈不空：在栈空时，我们不可以弹出栈里的元素，只能进入，所以队列里的数$-1$，栈里的数$+1$，即加上 $f[i-1,j+1]$ ；另一种是栈不空，那么此时有出栈$1$个或者进$1$个再出$1$个 $2$种情况，分别加上 $f[i-1,j+1]$ 和 $f[i,j-1]$ ，便是此时的情况了，于是递归就愉快的结束了；
感谢看完我的漫长的思路，但到了这里你就可以跟程序说再见了(代码最后给)；
2、**递推/$DP$(动态规划)**
------------
我们只要顺着递归的思路来就好了：
1. 据上面的递归，可知定义的 $f[i,j]$ 中 $i=0$ 时这个数组的值都为1，同时，这也是递推边界。并且，我们用 $i$ 表示队列里的数，$j$ 表示出栈数，$f[i,j]$表示情况数；
1. 既然我们愉快地得到了递推思路，愣着干嘛，因为即使初始化了我们也不可能直接用递归的思路写出递归！所以开始找规律：$f[i,j]$到底与什么有着不可告人的联系？其实这个很容易可以想到：当 $i$ 个数进栈，$j-1$ 个数出栈的时候，只要再出一个数，便是i个数进栈，$j$ 个数出栈的情况，同理，对于进栈 $i-1$ 个数，出栈 $j$个数，在进栈一个数便是$f[i,j]$了，于是就有了递归式：$f[i,j]=f[i-1,j+1]$.
1. 然而事实上这还没有完，因为 $i=j$ 时，栈空了，那么，此时就必须进栈了，则$i-1$，有$f[i,j]=f[i-1,j]$；解释一下为什么这样会栈空：当队列和出栈的数都有i个数时，数的总数为 $2i$ ，很明显的，栈里面没有元素了！
于是我们又快乐地解决了递推(其实就是$DP$)的做法，其实与递归大同小异，只不过一个通过函数实现，一个通过循环实现；但这还是基础啊~(代码后面给)
3、**数论做法 卡特兰/$Catalan$**
------------
既然很多Dalao都说过，那我直接给式子了；
- **递推式$1$：**
$f[n]=f[0]*f[n-1] + f[1]*f[n-2] + ... + f[n-1]*f[0] (n≥2)$
然后按照这个递推式模拟就好了(代码后面给)
既然上面标了1，那就有递推式2~
- **递推式$2$：**
$h[n]=h[n-1]*(4*n-2)/(n+1)$
依旧按式子模拟(代码后面给)
既然有2，那再来个3吧~
- **递推式$3$：**
$h[n]=C[2n,n]/(n+1) (n=0,1,2,...)$,$C$是组合数
$PS:C[m,n]=C[m-1,n-1]+C[m-1,n]$:且规定： $C[n,0]=1 C[n,n]=1 C[0,0]=1$
**这个公式也叫组合数公式(下面那个也是)**
（不知道组合数可以百度）
于是仍然把标程放到最后~
- **递推式$4$：**
$h[n]=C[2n,n]-C[2n,n-1] (n=0,1,2,...)$ 组合数$C$不解释了；
**~~没有$5$了~~**
但是有个Dalao写的组合数我没看懂，于是我搜集了各方资料，~~还是没看懂~~，不知道他写的组合数是怎么求的，虽然最后结果对了，但是组合数求出来都是错的(￣_￣|||)，~~不知道是不是巧合？~~
不管了，$AC$就好；（程序还是后面给~）
- 但是，出现了一个问题，上面介绍了四种公式，哪种最好？其实是第4种：如果这个数太大，那么题目可能会要求取模，那么第$1$种$n$太大的时候时空太大；第$2$种在取模运算中万一不小心整除了就凉了；第$3$种是除法运算，更行不通；唯有第$4$种,满足取模原则（加减无所谓），且不会出现倍数 $WA$ 的情况，所以第$4$种解为最优解；
- 接着，比较上面四种做法：很明显的，递推式长得差得不多，它们都源于卡特兰思想，那么就没什么好说的了，只是时空复杂度的不同而已；
**当然，已经有$3$种做法了，我再给一种：高精度/打表**
------------
这种做法可以避免一切 WA（~~打表出省一？~~）
所以我们随便拿一种写个高精？
然而并不是的，我们需要找一个好写的，那就是**卡特兰公式$1$！**
因为这就只是个加法，而且只是为了打表而已（~~我只熟悉加法orz~~）
**所有代码如下：**
------------
```cpp
//认真看，杜绝抄袭
//好好消化一下，这题很经典
//记忆化搜索/递归 做法
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N][MAX_N];
ll dfs(int i,int j)
{
if(f[i][j]) return f[i][j];
if(i==0)return 1; //边界
if(j>0) f[i][j]+=dfs(i,j-1);
f[i][j]+=dfs(i-1,j+1);
return f[i][j];
}
int main()
{
scanf("%d",&n);
printf("%lld",dfs(n,0));
return 0;
}
//递归转递推 递推做法
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N][MAX_N];
int main()
{
scanf("%d",&n);
for(int i=0;i<=n;i++)
{
f[0][i]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(i==j)f[i][j]=f[i-1][j];
else f[i][j]=f[i][j-1]+f[i-1][j];
}
}
printf("%lld",f[n][n]);
return 0;
}
//数论做法 卡特兰数
//公式1：
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N];
int main()
{
f[0]=f[1]=1;
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
for(int j=0;j<i;j++)
{
f[i]+=f[j]*f[i-j-1];
}
}
printf("%lld",f[n]);
return 0;
}
//公式2：
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N];
int main()
{
f[0]=f[1]=1;
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
f[i]+=f[i-1]*(4*i-2)/(i+1);
}
printf("%lld",f[n]);
return 0;
}
//公式3：
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll c[MAX_N*2][MAX_N];
int main(){
scanf("%d",&n);
for(int i=1;i<=2*n;i++)
{
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
{
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
printf("%lld",c[2*n][n]/(n+1));
return 0;
}
//公式4：
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll c[MAX_N*2][MAX_N];
int main(){
scanf("%d",&n);
for(int i=1;i<=2*n;i++)
{
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
{
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
printf("%lld",c[2*n][n]-c[2*n][n-1]);
return 0;
}
//高精/打表：
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX_N 110
using namespace std;
int f[MAX_N][MAX_N],c[MAX_N];
inline int len(int a[])
{
int i;
for(i=60;i>=0;i--)//想要100个以上，这个i的范围要改
{
if(a[i]!=0) break;
}
return i;
}
inline void add(int a[],int b[],int w)//高精加法
{
int lena=len(a),lenb=len(b);
for(int i=0;i<=max(lena,lenb);i++)
{
f[w][i]=a[i]+b[i];
}
for(int i=0;i<=max(lena,lenb)+1;i++)
{
f[w][i+1]+=f[w][i]/10;
f[w][i]%=10;
}
}
inline void Catalan(int a[],int b[])//卡特兰
{
memset(c, 0, sizeof(c));
int lena=len(a),lenb=len(b);
for (int i=0;i<=lena;i++){
for (int j=0;j<=lenb;j++)
c[i+j]+=a[i]*b[j];
}
for (int i=0;i<=lena+lenb+1;i++)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
int main()
{
//int k;
freopen("Catalan.txt","w"stdin);//文件操作;
f[0][0]=f[1][0]=1;
for (int i=2;i<=100;i++)//同理，要多输出几个i就等于几
{
for (int j=0;j<i;j++)
{
Catalan(f[j], f[i-j-1]);
add(f[i],c,i);
}
}
for(int i=1;i<=100;i++)//输出 卡特兰数 1-100，范围同上，要输出几个自己改
{
for (int j=len(f[i]);j>=0;j--)
{
//printf("%d",f[i][j]);
putchar((char)f[i][j]+'0');//比printf稍快?
}
printf("\n");
}
return 0;
}
```
虽然可能讲的不好，但是看我写了这么多，点个赞好吗 orz
------------