题目描述

X王国有n位官员，编号从1到n。国王是1号官员。除了国王以外，每个官员都有一个上司。我们称这个官员是这个上司的下属。上司的编号总比下属小。
我们定义一个官员的影响力为他所有下属的影响力之和再加1。例如，一个没有下属的官员的影响力是1。国王的影响力总是n。
任何一位有下属的官员总是选择他的下属中影响力最高的作为他的心腹（有若干下属影响力相同的话则会选择编号最小的）。
一位官员得到一条消息后，他就要把消息传达给国王。我们定义一位官员的花费为他将消息传达给国王的花费。国王自己的花费为0。如果一位官员是他上司的心腹，则他的花费等于他上司的花费，否则他的花费为他上司的花费加1。
由于时代和平，消息并不需要传递的太快。我们希望你决定每位官员（除了国王）的上司，使得所有官员的花费之和尽量大。

输入描述:

一个整数n（1≤ n≤ 8000）表示包括国王在内的官员的总数。

输出描述:

一个整数表示最大的花费之和。

题解

我们粗略的抽象一下题意。重儿子对于答案的贡献与其父节点相同，而其他节点对于答案的贡献则是其父节点+1。
图片说明
数字代表花费即贡献，红色节点代表重儿子。所谓重儿子，即父亲节点的所有儿子中子树结点数目最多（size最大）的结点。
如果我们一旦确定某父节点重儿子的节点数目，那么此父节点其他所有节点的大小都不能超过此重儿子的节点数目。我们设f[i]为树的大小为i时所能够构造出来的最大答案，现在来考虑递推这个答案。
在递推f[i]的时候，枚举心腹子树大小j,由于其他儿子的子树大小都不能大于j,因此递推公式：f(i)=max(f[j]+其他节点的花费),j<i。
现在我们怎么去求其他节点的花费呢？由于对于其他节点来说有大小的限制，我们设dp[i][j]表示满足一共有j个点的森林，森林中每棵树大小均不大于i的条件的所有点的深度和的最大值，即其对于答案的贡献。
那我们怎么去求dp[i][j]呢？如果我们已经有了f[i]和所有dp[k][j],k<i，我们可以把每个大小为i的子树看成一件物品，那么这就是一个完全背包，转移方程为dp[i][j]=max(dp[i-j][j]+f[j],dp[i][j-1])

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
int dp[8050],f[8050][8050];
////////////////////////////////////////////////////////////////////////
int main(){
    int n=gn();
    dp[1]=0;
    repi(i,1,n){
        repi(j,1,i){
            dp[i]=max(f[i-j-1][j]+dp[j]+i-j-1,dp[i]);
        }
        repi(j,1,n){
            if(i>=j)f[i][j]=f[i-j][j]+dp[j];
            else f[i][j]=f[i][j-1];
        }
    }
    print(dp[n]),putchar(10);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/