牛客国庆集训派对Day6(kingdom)

链接：https://www.nowcoder.com/acm/contest/206/F
思路：我们考虑对于一个n，因为国王是最高上司，所以国王就是树的根，那么整个的和的最大值就等于各个子树的和的最大值+总结点数-结点树最多的子树的结点个数-1，因为各个子树可以重复出现，让我们想起了多重背包，我们考虑用f[i]表示当前i个结点总和的最大值，用g[i][j]表示总和为j，其最大子树的总结点数不超过i时的最大值，那么我们就很容易得到状态转移方程：
f[i] = max(f[i],f[j] + g[j][i-j-1]+i-j-1); 1<=j<i
同时我们要维护整个g[i][j],当j<i时有
g[i][j] = g[i-1][j];
当j>=i时有
g[i][j] = max(g[i][j],g[i][j-i]+f[i]);
做一遍复杂度为（n^2）的dp即可
代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 8005;
int f[maxn];//f[i]:第i个点时的答案
int g[maxn][maxn];//g[i][j]，总和为j，最大子树和不超过i时的答案
int n;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++)f[i] = max(f[i],f[j] + g[j][i-j-1]+i-j-1);
        for(int j=1;j<=n;j++){
            g[i][j] = g[i-1][j];
            if(j>=i)g[i][j] = max(g[i][j],g[i][j-i]+f[i]);
        }        
    }
    printf("%d\n",f[n]);
    return 0;
}