[NOIP2003 普及组] 栈题解

# [NOIP2003 普及组] 栈 题解
[原题链接](https://www.luogu.com.cn/problem/P1044)

[数据加强版链接](https://www.luogu.com.cn/problem/U232071)

## 暴力深搜回溯

记录下当前的两个栈，按题意模拟，每一层分类讨论两个操作。

代码简单，这里就不呈现了。

连原题都过不了。

## 暴力深搜

可以发现，栈中的元素值对最终答案没有影响，所以只需要记录栈中的元素个数。

dfs传三个参数，分别表示现在输出序列的长度和两个栈的长度。

代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
long long res=0;
void f(int a,int b,int c){
   if(a==n){
     res++;
     return;
   }
	
	if(c>0){
	   f(a,b+1,c-1); 
    }
	if(b>0){
		f(a+1,b-1,c);
	}
}
int main(){
	cin>>n;
   f(0,0,n);
	cout<<res<<endl;
}
```
## 记忆化搜索
显然，每一次DFS都只有a,b,c三个参数对答案有影响，可以记忆化。记录当传入参数为i,j,k时对最终答案的影响。复杂度O(n^3)。

代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int f[25][25][25];
int dfs(int a,int b,int c){
	int res=0;
	if(f[a][b][c]){
		return f[a][b][c];
	}
	if(a==n){
		return 1;
	}
	if(b){
		res+=dfs(a+1,b-1,c);
	}
	if(c){
		res+=dfs(a,b+1,c-1);
	}
	f[a][b][c]=res;
	return res;
}
int main(){
	cin>>n;
	cout<<dfs(0,0,n);
}
```
## DP
既然可以深搜+记忆化了，那么DP肯定也行。

f[i][j][k]=f[i-1][j+1][k]+f[i][j-1][k+1]。

复杂度O(n^3)。

代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,dp[505][505][505];
int main(){
	cin>>n;
	dp[0][0][n]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int l=0;l<=n;l++){
				if(i)dp[i][j][l]+=dp[i-1][j+1][l];
				if(j)dp[i][j][l]+=dp[i][j-1][l+1];
			}
		}
	}
	cout<<dp[n][0][0];
}
```
## DP优化
可以发现，i,j,k总和是一致的，所以可以直接压掉一层，复杂度O(n^2)。

代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,dp[5005][5005];
int main(){
	cin>>n;
	dp[0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(i)dp[i][j]+=dp[i-1][j+1];
			if(j)dp[i][j]+=dp[i][j-1];
		}
	}
	cout<<dp[n][0];
}
```
## 递推
与DP类似，改成了递推的形式。从前往后推。

代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,dp[5005][5005];
int main(){
	cin>>n;
	dp[0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j+1]+=dp[i][j];
			if(j)dp[i+1][j-1]+=dp[i][j];
		}
	}
	cout<<dp[n][0];
}
```
## DP+空间优化
从递推可以发现，每一层内层循环都只涉及到dp数组的两位，直接开太费空间，可以只开两个数组来记录。

```cpp
#include <bits/stdc++.h>
using namespace std;
int n,dp[5005],l[5005];
int main(){
	cin>>n;
	l[0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++)dp[j]=l[j],l[j]=0;
		for(int j=0;j<=n;j++){
			dp[j+1]+=dp[j];
			if(j)l[j-1]+=dp[j];
		}
	}
	cout<<dp[0];
}
```
## 乘法原理+递推
思路和代码来自[Leowang2009](https://www.luogu.com.cn/user/696106)。

f[i]表示的是长度为i时的结果。

根据乘法原理，可得$f_i=\sum\limits_{j=0}^{i-1}f_j*f_{i-j-1}$。

直接求即可。

复杂度O(n^2)。

代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
bool b[2000005];
int n,a[2000005];
int main(){
	cin>>n;
	a[0]=1;
	a[1]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<i;j++){
			a[i]+=a[j]*a[i-j-1];
		}
	}
	cout<<a[n];
	return 0;
}
```

## 另一种DP
用$f_{i,j}$表示栈A入栈i次，出栈j次的方案数。

由于栈的大小不可能小于0，所以j<=i。

则$f_{i,j}=f_{i-1,j}+f_{i,j-1}$

代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int f[5005][5005],n;
int main(){
	cin>>n;
	f[0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(i)f[i][j]+=f[i-1][j];
			if(j)f[i][j]+=f[i][j-1];
		}
	}
	cout<<f[n][n];
}
```

## 终极优化
把$f$抽象到坐标轴上，$f_{i,j}$表示坐标轴上点(i,j)。

由于j<=i，所以问题就转化成了从坐标点$(0,0)$走到$(n,n)$，每次可以从$(i,j)$移到$(i+1,j)$或$(i,j+1)$且不经过直线$y=x$的方案数。

如果不考虑直线，则方案数为$C_{2n}^n$。

考虑不合法方案的种数。

不合法的原因显然是j>i，即超过了直线$y=x$，记为路线A。

显然，路线A一定碰到直线$y=x+1$。

将第一次碰到直线$y=x+1$后全部关于该直线对称。则终点变成了$(n-1,n+1)$

所以对于每一个不合法的路线，都能转化为从$(0,0)$到$(n-1,n+1)$

![D5C9w.png](https://s1.328888.xyz/2022/07/26/D5C9w.png)

方案数为$C_{2n}^{n+1}$。

所以总方案数为$C_{2n}^n-C_{2n}^{n+1}$。

直接求就行，复杂度O(n)。

代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,res,c[10000005],nw,sum=1;
int gc(int x){
	if(x>nw){
		for(int i=nw+1;i<=x;i++){
			sum*=i;
			c[i]=sum;
		}
		nw=x;
	}
	return c[x];
}
int main(){
	cin>>n;
	res=gc(2*n)/gc(n)/gc(n)-gc(2*n)/gc(n+1)/gc(n-1);
	cout<<res;
}
```