M04081: 树的转换

http://cs101.openjudge.cn/practice/04081/

代码：

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int depth[10001];
stack<int> stk;
vector<int> v[10001];

int main(){
	int id = 0, h1 = 0;
	string s;
	cin >> s;
	stk.push(0);
	for (char i : s){
		if (i == 'd'){
			id++;
			v[stk.top()].push_back(id);
			stk.push(id);
		} else {
			stk.pop();
		}
		h1 = max(h1, (int)stk.size() - 1);
	}
	for (int i = id; i >= 0; i--){
		int size = v[i].size();
		for (int j = 0; j < size; j++){
			depth[i] = max(depth[i], depth[v[i][j]] + j + 1);
		}
	}
	cout << h1 << " => " << depth[0];
	return 0;
}