题目描述 Description

 

思路：最近在练dp，看到题后也想到了树型dp，但是。。。实现起来很蛋疼。。。所以就另辟蹊径，先问了同组的yfy怎么手算，她神奇的似懂非懂的把我引上了一个神奇的思路，其实中序遍历的不同主要有那些只有一个儿子的结点的个数决定，而对于一个只有一个孩子的结点来说，他在前序和后序遍历中的位置很特殊，他在前序遍历中的后面一个结点一定是他在后序遍历前面的一个结点（证明十分简单，可以自己考虑一下），这样就很容易找到这些点，因为他们的孩子可能在左右两种情况，所以总个数就是2^(只有一个儿子的结点的个数)。这种神奇的思路也能很好的用到初赛中，解决了遍历中三种遍历的转换问题。

 

code：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    char ch1[30],ch2[30];
    int l,i,j,c=0,ans;
    cin>>ch1>>ch2;
    l=strlen(ch1);
    for (i=0;i<l-1;++i)
      for (j=l-1;j>=1;--j)
        if (ch1[i]==ch2[j]&&ch1[i+1]==ch2[j-1])
          ++c;
    ans=1;
    for (i=1;i<=c;++i)
      ans*=2;
    cout<<ans<<endl;
}