Thursday, December 3, 2015

*[topcoder]TheTree - 阿牧遥 - 博客园

*[topcoder]TheTree - 阿牧遥 - 博客园
 Manao is working in the Tree Research Center. It may come as a surprise that the trees they research are not the ones you can see in a park. Instead, they are researching special graphs. (See Notes for definitions of terms related to these trees.)Manao's daily job is reconstructing trees, given some partial information about them. Today Manao faced a difficult task. He needed to find the maximum possible diameter of a tree, given the following information: Some vertex in the tree is called V. The distance between V and the farthest vertex from V is D. For each x between 1 and D, inclusive, Manao knows the number of vertices such that their distance from V is x. You are given a int[] cnt containing D strictly positive integers. For each i, the i-th element of cnt is equal to the number of vertices which have distance i+1 from V. Please help Manao with his task. Return the maximum possible diameter of a tree that matches the given information.

https://github.com/phungleson/topcoder/blob/master/src/main/java/phungleson/topcoder/srm591/TheTree.java

`int` `TheTree::maximumDiameter(vector <``int``> cnt) {`
`    ``int` `D = cnt.size();`
`    ``int` `ans = 0;`
`    ``for` `(``int` `i = 0; i < D; i++) {`
`        ``int` `res = 0;`
`        ``int` `flag = ``false``;`
`        ``for` `(``int` `j = i; j < D; j++) {`
`            ``if` `(cnt[j] == 1)`
`                ``flag = ``true``;`
`            ``res += (flag ? 1 : 2);`
`            ``ans = max(res, ans);`
`        ``}`
`    ``}`
`    ``return` `ans;`
`};`