NC19810（kingdom ）

感受
$一道非常值得点赞的题目！这种树结构不知的题目，一看到我就害怕了，于是直接看了题解...下次就不会了$
思路
$解题思路很巧妙，可以先假设有一棵树，其大小为n，再假设该树的重儿子所在的树大小为num$
$那么这棵树对应的答案=重儿子所在树的贡献+（n-num-1）+$ $图片说明$
$注意：n-num-1表示子树构成的森林的点都要经过轻儿子再到达根(+1)$
$考虑到一个是树的贡献，一个是森林的贡献。于是可以设$
$ans[i]表示节点数为i的树最大贡献$
$dp[i][j]表示节点数为i的森林，且森林中每个子树的大小均小于等于j的最大贡献$
$更新方式如下：$
$ans[i] = max(ans[i], dp[i - j - 1][j] + ans[j] + i - j - 1);其中j表示枚举重儿子所在树的大小$
$dp[i][j]=max(dp[i][j], dp[i-k*j][j-1]+k*ans[j]);$
$ans数组更新可以在O(n^2)完成，但是dp数组由于k的引入需要O(n^3)完成，这会TLE$
$考虑如何优化DP数组的求解？$
$dp[i][j]=max(dp[i-0*j][j-1]+0*ans[j], dp[i-1*j][j-1]+1*ans[j], ...,dp[i-k*j][j-1]+k*ans[j])$
$dp[i-j][j]=max(dp[i-j][j-1]+0*ans[j], dp[i-2*j][j-1]+1*ans[j], ...,dp[i-k*j][j-1]+(k-1)ans[j])$
$=>dp[i][j]=max(dp[i][j-1],dp[i-j][j]+ans[j])$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 8e3 + 10;
ll ans[maxn], dp[maxn][maxn];
/**ans[i]表示i个节点构成的树最大贡献*/
/**dp[i][j]表示i个节点构成的森林中, |任意一棵树| <= j的最大贡献*/
int n;
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            ans[i] = max(ans[i], dp[i - j - 1][j] + ans[j] + i - j - 1);
        }
        for(int j = 1; j <= n; j++){
            dp[i][j] = dp[i][j - 1];
            if(i >= j){
                dp[i][j] = max(dp[i][j], dp[i - j][j] + ans[j]);
            }
        }
    }
    printf("%lld\n", ans[n]);
    return 0;
}