2012-06-30 08:07:51Morris
[PTC] 201206B Tree Balance 動態規劃
Problem B
Tree Balance
Input le: testdata.in
Time limit: 1 seconds
Problem DescriptionTree Balance
Input le: testdata.in
Time limit: 1 seconds
We have n nodes, each of them has its node number i and weight wi for the
i-th node. We want to construct a binary tree by these nodes such that the
sequence of node numbers of in-order traversal is from 1 to n. Figure 1 is
a possible tree when n is 5. The sequence of the node number of inorder
traversal of the tree is 1, 2, 3, 4, 5.
2
1 4
3 5
Figure 1: Example of possible tree when n is 5. Note that the weight of each
node is not shown here.
There are many trees meet the requirement. De ne S(T) as the sum of
the weights of all nodes in the tree T, V (T) as the skewing value of the tree
T, where V (T) = (S(TL) - S(TR))2 + V (TL) + V (TR). For an empty tree E
we de ne V (E) = S(E) = 0. Can you tell us the minimum skewing value of
these trees?
Technical Speci cation
1 N 100
0 wi 1000
Input Format
There are multiple test cases in the input. Each test case starts with a line
containing the number of nodes N. Then followed with a line, containing the
weights of the N nodes, separated by a white space.
Output Format
For each test cases, output the minimum skewing value of the N nodes in a
line.
Sample Input
1
4
4
1 2 3 4
Sample Output
0
2
題目意思 : 給一個中搜走訪的結果, 詢問其中一個根的 V(root) 最小
由於 V(T) 會加上左右子樹總合差的平方, 又因為是中序搜尋的結果,
因此可以想成左邊當作左子樹, 右邊當作右子樹, 就會得到下面的遞迴式,
窮舉要當成樹的根的地方, 寫遞迴比較好寫, 記住答案可能會超過 int 的範圍
#include <stdio.h>
#include <string.h>
long long dp[101][101] = {}, w[101] = {};
long long dfs(int i, int j) {
if(dp[i][j] != -1)
return dp[i][j];
long long min = 0xfffffffffffffffLL, tmp;
int k;
for(k = i; k <= j; k++) {
tmp = dfs(i, k-1) + dfs(k+1, j) + (w[j]-w[k]-w[k-1]+w[i-1])*(w[j]-w[k]-w[k-1]+w[i-1]);
if(tmp < min)
min = tmp;
}
dp[i][j] = min;
return dp[i][j];
}
int main() {
int n, i;
while(scanf("%d", &n) == 1) {
memset(dp, -1, sizeof(dp));
for(i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
w[i] += w[i-1];
dp[i][i] = 0;
dp[i][i-1] = 0;
}
printf("%lld\n", dfs(1, n));
}
return 0;
}