kingdom

题意：
有一棵节点数为n的树，每一个子节点向父节点传送消息时，如果以父节点为根的子树中该节点为根的子树中节点数最多，则该节点花费为父节点的花费，否则为父节点花费+1.求所有节点一层一层向根节点传送消息的花费之和尽量大时的花费为多少？

思路：
这题我们可以用dp解决，我们求的是n个节点树的最大花费，所以我们设sum[i]为节点数为i的树的最大花费，我们知道节点数最多的子树（设节点数为x）传送消息的花费为父节点的花费，相当于该子树节点向根节点传送信息花费为0，而其他子树的节点向根节点传送信息花费为1，又因为子树的花费是树的花费的一部分，所以树的最大花费为=（ sum[子树] ）+其他子树的节点个数；
我们如果把其他子树单独看则是一个森林，且该森林中的树节点数小于等于x,所以我设dp[i][j]为节点数为i的森林每棵子树节点数小于等于j的最大花费。
所以sum[i]=（dp[i-x-1][x]+sum[x]）（所有子树的花费）+(i-x-1)(其它节点树的节点个数)。
dp[i][j]=max(dp[i][j-1],dp[i-j][j]+sum[j]);(第一种情况是当i<j时森林的节点数i<=j和i<=j-1等价，第二种情况时往节点数等于（i-j）的最大花费森林中加一棵节点数为j的最大花费树时不就是节点数为i的最大花费森林吗)。

代码：

#include <bits/stdc++.h>
#define inf 1000000007
#define eps 0.000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn=100005;

inline int read()
{
    char c=getchar();
    int f=1, x=0;
    while(c>'9'||c<'0')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f*x;
}

int sum[10005], dp[10005][10005];

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