【每日一题】 kingdom

动态规划。

根据题意直接构造出树比较难，所以采用动态规划的方法。

记ans[i]表示当树有i个结点时所求花费的最大值。
假设在考虑有i个结点时，我们已经知道了结点数小于i时的ans，则可以通过ans[i]=max(ans[i],ans[j]+???)得到答案，其中j为结点数为i时所有可能的重儿子，也就是题目中所说的“官员的心腹”。现在只需将“???”求出来。

理解“???”是什么意思，不妨先看看转移方程中缺什么。在选定了重儿子的同时其贡献也求了出来，即ans[j]，现在需要安排轻儿子：求出轻儿子的贡献同时确保其小于重儿子。这就要求将除重儿子以外的结点分成若干组，每组结点数不能大于j。因此，我们再定义：f[i][j]表示将i个结点分成若干组（每组各有一个根节点）且每组不大于j个时，得到的最大花费。

由此第一个转移方程便求出来了：ans[i]=max(ans[i],ans[j]+f[i-j-1][j]+i-j-1)。
为什么要加上后面“i-j+1”这一串？因为f[i][j]分组后每组实际上是一棵子树，现在需要将子树连接到根节点上，由于其为轻儿子（也就是非心腹大臣），自然要在子树的根节点上加一，而后所有子树便都要加一，其大小正好为“i-j+1”。

下面考虑第二个转移方程，最直接的想法是：f[i][j]=f[i-j][j]+ans[j]。显然这没有考虑到所有的情况。观察第一个转移方程，f[i-j-1][j]中，f[][]两个方括号里的大小关系是不缺定的，而在第二个转移方程中的“i-j”就直接说明了i>=j，得到的f[i][j]范围肯定是小了。

所以，现在要考虑当i<j时的情况。咋考虑？当然要从f的定义入手。
f[i][j]是要将i个分组，每组不超过j个。那么现在假设i已经小于j了，将i个分组，每组不超过j个，j+1个，j+100个，都是一样的，一组最多只有i个。
所以第二个转移方程如下：
f[i][j]=f[i-j][j]+ans[j]; //(i>=j)
f[i][j]=f[i][j-1]; //(i<j)

最后通过两个转移方程即可逐步求出ans[n]。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=8e3+9;
const ll maxx=1e12+9;

int n;
int ans[maxn],f[maxn][maxn];

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