HDU 5534 Partial Tree (完全背包变形)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5534

题意：

        给你度为1 ~ n - 1节点的权值，让你构造一棵树，使其权值和最大。

思路：

        一棵树上每个节点的度至少为1，且度的和为2*n - 2。那么我们先给这些节点的度都-1，剩下的节点度为n - 2。此时我们发现，任意分配剩下的这些度给节点，都可以形成一棵树。这就变成了一个完全背包题，容量为n-2。注意dp要初始化为-inf。思路确实巧妙。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2020;
int a[N], inf = 1e8;
int dp[N];
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n - 1; ++i) {
            scanf("%d", a + i);
            dp[i] = -inf;
        }
        for(int i = 2; i <= n - 1; ++i) {
            for(int j = 1; j <= n - 2; ++j) {
                if(j >= i - 1) {
                    dp[j] = max(dp[j], dp[j - i + 1] + a[i] - a[1]);
                }
            }
        }
        printf("%d
", dp[n - 2] + n*a[1]);
    }
    return 0;
}