~~小学生来水题解了~~

先看题目,你的程序将对给定的

n

，计算并输出由操作数序列

1,\dots,n

经过操作可能得到的输出序列的总数。(

n \le 18

)~~啊， $n$ 这么小，可以 $O(2 ^ n)$ 暴力了~~

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

CPP

#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

)的值。

CPP

#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}

;

CPP

#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]);
}

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

文章操作

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

动态规划

完结撒花

相关推荐

评论

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

文章操作

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

动态规划

完结撒花

相关推荐

评论

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