4081:树的转换
总时间限制: 5000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB
描述
我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树，如：
0 0
/ | \ /
1 2 3 ===> 1
/ \ \
4 5 2
/ \
4 3
\
5
现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。
输入
输入是一个由“u”和“d”组成的字符串，表示一棵树的深度优先搜索信息。比如，dudduduudu可以用来表示上文中的左树，因为搜索过程为：0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。
你可以认为每棵树的结点数至少为2，并且不超过10000。
输出
按如下格式输出转换前和转换后树的高度：
h1 => h2
其中，h1是转换前树的高度，h2是转换后树的高度。
样例输入
dudduduudu
样例输出
2 => 4
问题链接：Bailian4081 树的转换
问题简述：（略）
问题分析：用dfs解决，不解释。
程序说明：（略）
参考链接：（略）
题记：（略）
AC的C++语言程序如下：
/* Bailian4081 树的转换 */
#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
char s[3 * N];
int k, r1, r2;
void dfs(int d1, int d2)
{
r1 = max(r1, d1);
r2 = max(r2, d2);
int cnt = 1;
while(s[k]) {
if(s[k] == 'd') {
k++;
dfs(d1 + 1, d2 + cnt++);
} else {
k++;
break;
}
}
}
int main()
{
scanf("%s", s);
r1 = r2 = -1;
k = 0;
dfs(0, 0);
printf("%d => %d\n", r1, r2);
return 0;
}