NC19810 kingdom题解

分析：

开始看到这个题的时候，我就想着去构造这样一棵树，可是构造失败了。
这个题的数据范围是8000，其实已经提示了构造可能是不可行的，否则这个数据范围要更大才对。
于是看了大佬的题解,想了好长时间才恍然大悟。

树形结构有着很好的对称性，这种对称性是指当拿掉一个结点后，这个结点所连接的几个部分仍然是树。这就意味着一个子树上的答案的求解过程很有可能和这个结点上的答案的求解过程有一定的相似性。和在遇到树形结构的问题时可以先思考一个结点上的答案是否可以由它的子树转移而来，从而将问题的规模缩小。这也是树形DP的基本思路之一。
这个题有下面几个特点：

1. 一个结点的子树中，有一个特殊的“心腹”
2. 树的结构不确定，题目中描述的只有树的规模
3. 数据规模在8000以内

设数组ans[i]记录的是问题规模为i时的答案，思考一下ans[i]是否能由and[0..i-1]转移而来呢。
因为这个题目中每个结点的儿子数量未知，再加上“心腹”的存在，让这个思路很难进行下去。
因为ans[i]可以由其子结点的值答案得到。如果把根结点去掉剩下，以它的子节点为根的树构成了一个森林。用dp[i][j]表示节点数小于等于i且最大结点不超过j的森林的答案的和的最大值。

于是有以下转移方程： $ans\left[ i \right] =\max \left( ans\left[ i \right] ,dp\left[ i-1-k \right] \left[ k \right] +ans\left[ k \right] +i-1-k \right) \left( 0<k<i \right)$
$dp\left[ i \right] \left[ j \right] =\max \left( dp\left[ i \right] \left[ j \right] ,\ dp\left[ i \right] \left[ j-1 \right] \right)$
$dp\left[ i \right] \left[ j \right] =\max \left( dp\left[ i \right] \left[ j \right] ,dp\left[ i-j \right] \left[ j \right] +ans\left[ j \right] \right)$
实现的时候需要留意一下更新顺序

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=1e4+20;
const int INF=0x3f3f3f3f;
const LL MOD=998244353;
int dp[MAX_N][MAX_N];
int ans[MAX_N];
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen("1.in","r",stdin);

    cin>>n;
    for(int i=1;i<=n;i++){
        for(int k=1;k<i;k++){
            ans[i]=max(ans[i],dp[i-1-k][k]+ans[k]+i-1-k);
        }
        for(int j=1;j<=n;j++){
            dp[j][i]=max(dp[j][i],dp[j][i-1]);
            if(j>=i)dp[j][i]=max(dp[j][i],dp[j-i][i]+ans[i]);
        }
    }
    cout<<ans[n]<<endl;
}