kingdom

题意：
X王国有n位官员，编号从1到n。国王是1号官员。除了国王以外，每个官员都有一个上司。我们称这个官员是这个上司的下属。上司的编号总比下属小。
我们定义一个官员的影响力为他所有下属的影响力之和再加1。例如，一个没有下属的官员的影响力是1。国王的影响力总是n。
任何一位有下属的官员总是选择他的下属中影响力最高的作为他的心腹（有若干下属影响力相同的话则会选择编号最小的）。
一位官员得到一条消息后，他就要把消息传达给国王。我们定义一位官员的花费为他将消息传达给国王的花费。国王自己的花费为0。如果一位官员是他上司的心腹，则他的花费等于他上司的花费，否则他的花费为他上司的花费加1。
由于时代和平，消息并不需要传递的太快。我们希望你决定每位官员（除了国王）的上司，使得所有官员的花费之和尽量大。
题解：
看了大佬的题解才理解的。
在求第i个结点的最优解时，
重儿子所在子树节点数为j，非重儿子所在子树节点个数总和为i-j-1
那么ans就可以得出

对于第二个转移方程即为：
dp[i][j]=dp[i-j][j]+ans[j];(i>=j)
dp[i][j]=dp[i][j-1];(i<j)

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <cctype>
#include<iomanip>
//#define int long long
#define endl '\n'
using namespace std;
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
using namespace std;
int dp[maxn][maxn];
int ans[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            ans[i]=max(ans[i],ans[j]+dp[i-j-1][j]+(i-j-1));
        }
        for(int j=1;j<=n;j++){
            if(j>=i)    dp[j][i]=max(dp[j][i-1],dp[j-i][i]+ans[i]);

            else    dp[j][i]=dp[j][i-1];
        }
    }
    cout<<ans[n];
    return 0;
}