NC19810 kingdom（dp）

想不到的一道题，有点背包的感觉，但是重点还是题目所给的信息

首先观察题目应该是平方算法

进一步剖析，我只能想到枚举重儿子大小这个思路。

后来看了题解发现他们把信息挖掘的很到位。重儿子肯定是要枚举

现在求的是最大代价，而除了重儿子外，自顶向下的思路上看，还有很多其他子树，这些树组成了森林

如果求他的最大代价比较关键，题目其实没啥信息，有的比如节点个数，最大是平方算法，其他儿子不能大于所选的重儿子，所以把这些信息结合起来产生了一种状态设计f[i][j]

表示以i个节点，最大的子树个数不超过j的森林的最大代价。

这样就可以枚举更新了，而这个dp，因为是最大，所以首先要从f[i][j-1]更新过来，因为子状态包括他，其次就要考虑节点个数的变化

那么这个森林的更新就可以枚举，用ans[j]+f[i-j][j]这样的状态去更新，因为森林肯定是很多树，我们枚举其中一棵树的大小，那么其他树仍然组成了一个森林，并且因为这是小状态所以已经被计算了。

这样从宏观上理解就比较清晰了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=3e5+10;
int f[8080][8080];
int ans[N];
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++){
        for(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(j>=i)
                f[j][i]=f[j][i-1];
            if(j>=i)
                f[j][i]=max(f[j][i],f[j-i][i]+ans[i]);
        }
    }
    cout<<ans[n]<<endl;
}