HDU 5534 Partial Tree（dp优化）

题目链接：
HDU 5534 Partial Tree
题意：
有一棵树有$n$个节点，对于度为$d$的节点对树的价值贡献为$f(d)$，给出$f(1),f(2),\cdots ,f(n-1)$，(边是任意构造的)。求树的最大价值？
数据范围：$n\leq 2015$
分析：
一个$n$个节点的树会有$n-1$条边，每条边可以贡献两个度，所以总度数为$2*n-2$。很容易想到的状态定义是：

$$用dp[i][j]表示i个节点用掉j个度可以获得的最大代价$$
状态转移也很好想，枚举第 $i$个节点用掉的度为 $k$:
$$dp[i][j]=max(dp[i-1][j-k]+f[k]),\quad 1\leq k \leq j-i+1$$
这样子做的时间复杂度是 $O(n^3)$，做的时候一直在想怎么优化，但是无论怎么优化都要枚举，复杂度都不会降下来。看了题解，很服气o(╯□╰)o。
状态的定义很重要，其实就是思考的角度。
当时考虑到了一定会有至少两个点的度为1，所以直接求 $dp[n-2][2*n-4]$，最后再加上 $2*f[1]$即可。但是，再往深了想一想，实际上每个节点的度都大于等于1，所以我们可以先给每个节点附上一个度，那么接下来在考虑时就不用考虑节点度为0的情况了（这也是合法的）。那么还剩下 $n-2$个度。
$$Ans=max(\sum{(f[d_i+1]-f[1])})+n*f[1],d_i是每个节点在剩下的n-2个度中额外赋予的度$$
$$定义dp[i]表示用掉剩下的n-2个度中的i个可以获得的树的最大价值$$
这时我们不需要考虑前面 $n-1$个节点每个节点的度，因为已经保证了每个节点的度都会是合法的，只需要枚举第 $n$个节点在这 $i$度中又使用了多少个度：
$$dp[i]=max(dp[i-j]+f[j+1]-f[1])$$
$$Ans = dp[n-2]+n*f[1]$$
这样子把复杂度硬生生的降到了 $O(n^2)$，太巧妙了！

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <climits>
using namespace std;
typedef long long ll;
const int MAX_N = 2020;int T, n;
int f[MAX_N], dp[MAX_N];int main()
{scanf("%d", &T);while (T--) {scanf("%d", &n);for (int i = 1; i < n; ++i) {scanf("%d", &f[i]);}memset(dp, 0, sizeof(dp));for (int i = 1; i <= n - 2; ++i) {dp[i] = f[i + 1] - f[1]; // 把i个全赋给第n个节点for (int j = 0; j < i; ++j) { // 枚举第n个节点的额外赋予度数dp[i] = max(dp[i], dp[i - j] + f[j + 1] - f[1]);}}printf("%d\n", dp[n - 2] + n * f[1]);}return 0;
}