NOIP2003 栈 题解

动态规划($DP$:$Dynamic$ $Programming$)解法

1.思路：

这道题一眼给我们的感觉就是方案数太多了，而且利用暴力DFS是可以解决的，但是效率太慢。此时我们就应该思考一下DP了。
(1) $f(i,j)$表示的是，队列中的有$i$个元素，栈中有$j$个元素的时候，能够输出的栈序列总数。
(2) 状态转移 一般情况下，我们面临的只有两种方式：
要么让队列中的元素入栈:$f(i-1,j+1)$
要么就是让队列中的元素不动，栈中的元素出队。
所以方程是：$f(i,j-1)$

(3)循环设计
循环的设计是为了保证每次利用状态转移方程求解问题的时候，方程右侧的子问题已经在此之前正确的求解。
如果说的高端一些，就是我们的循环设计要满足拓扑排序。
我们看方程：
在算$f(i,j)$的时候，我们要知道的子问题答案有：
$f(i-1,j+1)$和$f(i,j-1)$
所以我们的外循环枚举$i$,内循环枚举$j$。如果反过来的话，我们会发现，我们含$j+1$的那一项无法在此之前算出。
(4)初末状态
初始状态是为了初始化最小的子问题，末尾状态是为了表示我们的答案。
我们的初始状态即当栈中的元素是j个，队列中的元素是0个的时候，我们只能出栈。此时只有1种序列。
还有就是当我们的队列中的元素只有1个，我们的栈中元素的个数是0的时候，我们此时的序列也是只有一种。
我们的最终状态是，队列中的元素个数是n，栈中的元素个数是0。即f[n][0]

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20;
int f[N][N];
int main()
{
    int n;
    cin>>n;
    f[1][0]=1;
    for(int i=0;i<=n;i++)
        f[0][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(j!=0)
                f[i][j]=f[i-1][j+1]+f[i][j-1];
            else
                f[i][j]=f[i-1][j+1];
        }
    }
    cout<<f[n][0]<<endl;
    return 0;
}