Optimal Cut

A cut of a binary tree is a set of tree nodes such as for each possible path from the root node to any leaf node, just one node in the cut belongs to the path. In a weighted binary tree, one can compute a weighted cut, because it would include weighted nodes. The total weight of such cut can be computed by adding up the weights of the nodes in it. The figure below shows a weighted binary tree. The gray nodes represent a weighted cut, and its total weight is 14.

Now, given a weighted binary tree, you have to write a program that finds the weighted cut with the maximal total weight value among all possible weighted cuts in the tree. This is hereafter called the Optimal Cut of the input binary tree. However, to make it a bit more interesting, your program must find the optimal cut that includes no more than K nodes, and report its weight. In the figure above, for instance, the nodes of the optimal cut sums 28 when K = 3, and 15 when K = 2.

Input 

The input can contain several problems. Each problem contains the description of a complete binary tree in a single line. This description corresponds to sequence of integer numbers, separated of each other by a blank space. The description starts with an integer 0H < 20 representing the height of the tree, followed by another integer 1K20 representing the maximum number of nodes in the optimal cut to be found. Then, the weights -10³Wi10³ of the nodes follow, listed in pre-order. The end of input is indicated by a single line containing only an integer value of `-1'.

Output 

For each problem in the input, the output should be a single line with a single integer number, representing the total weight of the optimal cut found.

Sample Input 

2 3 8 6 7 -2 -1 2 1
0 1 1
3 3 -8 1 0 0 1 2 1 1 -1 1 1 1 3 1 4
-1

Sample Output 

9
1
5

---

題目要求至多 K 個節點拔除，使得葉節點無法到達跟節點，
而在葉節點到達根節點的時候，只能有一個被拔除的節點。
而題目給你的樹是一個 complete binary tree。

因此動規的方程就可以從
(1) 左節點使用 1~K 個的最大值 配上 右節點使用 1~K 個的最大值
(2) 使用自己
得到。
如果不加優化輸入，程式碼是很短的。

#include <stdio.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
int H, K, i, j;
int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
void dfs(int dep, short dp[]) {
    int v;
    ReadInt(&v);
    if(dep == H) {
        dp[1] = v;
        return;
    }
    short l[K+1], r[K+1];
    for(i = 1; i <= K; i++)
        l[i] = r[i] = -0xfff;
    dfs(dep+1, l);
    dfs(dep+1, r);
    for(i = 1; i <= K; i++) {
        for(j = K-i; j >= 1; j--) {
            dp[i+j] = max(dp[i+j], l[i]+r[j]);
        }
    }
    dp[1] = max(dp[1], v);
}
int main() {
    while(scanf("%d", &H), H >= 0) {
        scanf("%d", &K);
        short dp[K+1], ans = -0xfff;
        for(i = 0; i <= K; i++)
            dp[i] = -0xfff;
        dfs(0, dp);
        for(i = 1; i <= K; i++)
            ans = max(ans, dp[i]);
        printf("%hd\n", ans);
    }
    return 0;
}

---