每日一题 7月13日 Kingdom 两个树形DP

题目链接：https://ac.nowcoder.com/acm/problem/19810
题目大意：

思路：我们定义DP[i]:i个节点形成的树的最大花费。
我们知道重儿子是一个费用的影响因素：那么我们枚举重儿子的节点个数为x。
因为除了重儿子，其他节点到根都有费用。
DP[i]=max(DP[i], DP[x]+DP[i-x-1]+i-x-1)
这个DP[i-x-1]是有问题的。因为重儿子的节点树必须小等于x。
我们定义：f[i][j]:i个节点组成的森林(多个树)，（因为和根断开后，这些都是子树），并且最大的那棵树节点数<=i的最大代价。

• 那么上面的方程为DP[i]=max(DP[i], DP[x]+f[i-x-1][x]+i-x-1)
  我们考虑f数组怎么转移：
  可以直接继承最大节点数==j-1的结果。我们可以考虑拆分子树。并且子树的大小为j。因为这样的子树最大大小一定小等于j.
• f[i][j]=max(f[i][j-1], f[i-j][j]+DP[j])

我们考虑怎么转移。我们先得到DP[j]。然后去把所有f[i][j]全部推出来。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL f[8005][8005], dp[8005];
int main() {
    LL n; scanf("%lld", &n);
    for(LL i=1; i<=n; i++){
        for(LL x=1; x<i; x++){
            dp[i]=max(dp[i], dp[x]+f[i-x-1][x]+i-x-1);
        }
        for(LL x=1; x<=n; x++){
            f[x][i]=f[x][i-1];
            if(x>=i){
                f[x][i]=max(f[x][i], f[x-i][i]+dp[i]);
            }
        }
    }
    printf("%lld\n", dp[n]);

    return 0;
}