ccpc wannafly 秦皇岛E kingdom【树形dp】【已修正】

这个题目是一个树形dp ，我们记F[i] 为 总数为i的时候的结果，
g[i][j] 表示的 总数为i ，心腹的子树结点为j的情况
所以，根据背包 g[i][j] = max(g[i][j-1],g[i-j][j]+f[j])
第一种情况就是多出的一个结点接在左边，那么这个节点作为心腹的话，就不会有贡献，另一种情况就是把结点接在右边，那么左边j个结点作为心腹的话，最多为f[j] 然后其余的i-j-1个结点在右边 的时候应该会多出 i-j+1的贡献，所以我们在计算 f[j]的时候要把这一部分算上。。

之前只过了一部分的数据，直到牛客重现了，看了大佬的代码，才修正了
我们在更新g[i][j]的时候 我之前只更新了一部分，应该要更新到n才对

#include <bits/stdc++.h>
using namespace std;
const int maxn=8000+100;
typedef long long ll;
int f[maxn];
int g[maxn][maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i]=max(g[i][j]+(i-j-1),f[i]);
        }
        for(int j=1;j<=n+1;j++)
        {
            if(j<=i)
            g[i+1][j] = max(g[i+1][j-1],g[i+1-j][j]+f[j]);
            else g[i+1][j]=g[i+1][j-1];
        }
    }

    printf("%d\n",f[n]);

    return 0;
}