【每日一题】Kingdom 题解

Description

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

Solution

显然，题目表示的关系可以抽象为树形结构，从题目的影响力最高作为心腹这句话可理解为树的重儿子。
那么原问题转换成树形dp问题，枚举重儿子的个数 ，
令

• 表示 个节点的最大花费
• 表示 个节点组成的森林，最多节点的树不超过 的最大花费

有转移方程
这里 是当前的重儿子为 , 那么其他儿子一共有 个，一边维护 即可
最后输出 即可

Code

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
typedef long long ll;

long long dp[8005], f[8005][8005];
// dp[i]: i 个节点的最大花费， f[i][j] i个节点分成若干组 每组不大于j的最大花费
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  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] << "\n";
  return 0;
}