题解：P1044 [NOIP 2003 普及组] 栈

· · 题解

小学生来水题解了

先看题目,你的程序将对给定的 n，计算并输出由操作数序列 1,\dots,n 经过操作可能得到的输出序列的总数。(n \le 18)啊，n这么小，可以O(2 ^ n)暴力了

暴力很简单,对于每次递归，来实现一下pop和push操作。

#include<iostream>
int n;
int dfs(int s,int k){
    if((2*n)==s){
        if(k==0) return 1;
        else return 0;
    }
    int t=0;
    if(k<=n) t+=dfs(s+1,k+1);
    if(k>0) t+=dfs(s+1,k-1);
    return t;
}
int main(){
    scanf("%d",&n);
    printf("%d",dfs(1,1));
}

然后就会快乐地TLE

原因:同一个部分会被重复计算

举例:

n=4

dfs(1,1)=dfs(2,2)+dfs(2,0);

dfs(2,2)=dfs(3,3)+dfs(3,1);

dfs(2,0)=dfs(3,1);

dfs(\normalsize 3,\normalsize 1)计算了\normalsize 2次!

那么，如何优化呢？

可不可以用数组存下答案呢？

回答正确，加10分

用a_{i,j}表示dfs(i,j)的值。

#include<iostream>
int n;
int a[40][20];
int dfs(int s,int k){
    if((2*n)==s){
        if(k==0) return 1;
        else return 0;
    }
    int t=0;
    if(a[s][k]!=0) return a[s][k];
    if(k<=n) t+=dfs(s+1,k+1);
    if(k>0) t+=dfs(s+1,k-1);
    a[s][k]=t;
    return t;
}
int main(){
    scanf("%d",&n);
    printf("%d\n",dfs(1,1));
}

然后就可以快乐的AC了

动态规划

刚才我们所使用的算法叫记忆化搜索,那么它再level up就成了动态规划。

因为每次pop操作前至少有一个push，那么就跟这道题一模一样。

考虑dp_{i,j}表示还有i个push和j个pop。

有两种情况,push和pop。

push：可以抵消一个pop,则dp_{i,j}+=dp_{i,j-1};

pop：消耗一个push，则dp_{i,j}+=dp_{i-1,j};

转移方程:dp_{i,j}=dp_{i,j-1}+dp_{i-1,j};

#include<iostream>
int n,dp[19][19];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) dp[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
    printf("%d",dp[n][n]);
}

完结撒花