AcWing 3486. 前序和后序 Python写法
原题链接
简单
作者:
是小肖啊
,
2022-04-26 19:41:48
,
所有人可见
,
阅读 334
M=21
dp=[[0 for i in range(M)]for j in range(M)]
for i in range(M):
for j in range(i+1):
if j==0:
dp[i][j]=1
elif j==1:
dp[i][j]=i
else:
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
def dfs(pre,post):
if len(pre)==1:
return 1
if pre[1] == post[len(post) - 2]:
cur = dp[n][1]
child = dfs(pre[1:], post[:len(post) - 2 + 1])
else:
cur=0
child=1
i,j=1,0
while i<len(pre) and j<len(post)-1:
lhead=pre[i]
ends=post.index(lhead)
length=ends-j+1
childpre=pre[i:i+length-1+1]
childpost=post[j:j+length-1+1]
cur+=1
child*=dfs(childpre,childpost)
i+=length
j+=length
cur=dp[n][cur]
ans=cur*child
return ans
try:
while True:
n,pre,post=input().split()
n=int(n)
ans=dfs(pre,post)
print(ans)
except EOFError:
pass