题目

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

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

输出描述：
一个整数表示最大的花费之和。

解析

1）知识点

这道题的考点就是树形dp，其实这道题我并不是很懂。

2）看题目

题目的意思就是说，我们现在要求花费。
如果是心腹就和上级一样，如果不是则+1。国王为0。
有个限制条件就是，一个下级只有一个上级，而且下级的上级，必须编号比自己小。

3）算法分析

  1. 首先我们假设k个子树大小分别为sum1,sum2.....sumk。
  2. 根据题目来说，我们可以得到(sum1+sum2+..+sumk+1)=n（因为一个下级只有一个上级）。
  3. 接下来当有一个不是心腹的下级存在的时候，相当于所有的下级的花费要+1（因为是心腹就和上级一样，如果不是则+1）。
  4. 所以我们还可以得到ans[n]=(ans[sum1]+ans[sum2]+...+ans[sumk])+(n−sumX−1)。
  5. 既然这道题都知道了是dp：动态规划最重要的就是递推和dp数组的含义。
  6. 那么dp数组是什么呢（下面用作f数组）：
    1. dp[i][j]表示 i个节点组成的森林(多个树)，且节点最多的那个树节点数不超过j。
  7. 然后转移方程根据上面也可以得出：
    1. 1.dp[i][j]=dp[i][j−1] ，小于等于j-1必定小于等于j，可以直接更新。
    2. 2.dp[i][j]=dp[i−x][j]+ans[x] ，x<=j, 由一棵节点数为x的树和一个节点总数为i-x的森林，且这个森林的节点最多的那棵树不超过j组成节点总和为i，节点最多的树不超过j的森林。

4）算法操作

  • 我们这里用一个循环来遍历所有情况（主要是思考难，题解简单）： 
    for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++)
        dp[i] = max(dp[i], dp[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] + dp[j];
        else f[i][j] = f[i][j - 1];
}

5）打代码

  1. 打代码呗
  2. 首先是输入数据
  3. 然后按递推式递推就好了
  4. 看下面代码呗~

AC代码 

#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int MAX = 8e3 + 7;
int dp[8005], f[8005][8005];

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++)
            dp[i] = max(dp[i], dp[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] + dp[j];
            else f[i][j] = f[i][j - 1];
    }
    cout << dp[n] << endl;
    return 0;
}