题目链接：http://www.wikioi.com/problem/1029/
算法：DP
本题有个2小技巧。
- 一棵二叉树的前序遍历a1a2a3...ai和后序遍历b1b2b3...bi有一种关系：当只有一棵子树的根 在a序列下标为i，
在b序列下标为b
有 a[i-1] == b[j+1]
这是因为当根只有一棵子树时，前序和后序遍历都是先遍历它的孩子，而且是唯一的一个孩子，所以相对位置是一样的。 - 当确定了一棵树的前序和后序遍历时，可以得到用如上方法找到只有一棵子树的根，并且因为上面的性质，子树在为左子女还是右子女并不影响前序后序的顺序，但影响中序遍历的顺序，而可以假设子树为左子女也可以假设为右子女，那么我们得到：
根据前后序得到中序遍历的数量 = 只有一个子女的根 ^ 2
那么答案就好求啦~
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <iostream>#include <string>using
namespace
std;
int
i, j, s, c;
int
main() {
string a, b;
cin >> a >> b;
s = a.size();
for(i = 1; i < s; ++i) for(j = s-2; j >= 0; --j) if(a[i] == b[j] && a[i-1]==b[j+1]) c++;
cout << (1<<c);
return
0;
} |