NC19810（dp）

https://ac.nowcoder.com/acm/problem/19810
这题有个结论比较好猜……
题目大意是，给定n要求构造一棵权值最大的树，如果一个点是父亲的重儿子，那么权值等于父亲，否则等于父亲权值+1，根权值=0。
设i个节点的树的最大权值是dp[i]，然后当我们想构造一棵大小为n的树时，根节点是0，接下来n-1个点形成一个森林，设其中最大树大小为k，那么dp[n]的值就由这些子树的dp值构成，其中，对于除了重子树的节点，都有额外的权值1，所以dp[n]=dp[k]+sum(dp[ai])+n-1-k,其中sum(ai)=n-k-1,max(ai)<=k。
所以核心算法就是，对于固定的n遍历其最大树k，然后对于每个k，找到合法森林的最大权值再加上n-k，这里的难题在于我们不知道对于剩下n-k个顶点如何构建出最大权值的森林。这时可以大胆做出一个猜测：将剩下n-k个点尽可能凑成k大的树，剩余不足的单独一棵树。因为最终结果一定是这种结构的，如果不是的话说明有别的树“性价比”更高，那就尽可能采用那棵树好了。
当然这个猜想也没证明正确，嘤嘤嘤，希望证实/伪的大佬可以分享一下

#include<bits/stdc++.h>
using namespace std;

const int maxn=8004;

int dp[maxn];

int main(){
    int n;
    cin>>n;
    for(int i=3;i<=n;i++){
        for(int j=1;j<i;j++){
            dp[i]=max(dp[i],(i-1)/j*dp[j]+dp[(i-1)%j]+i-1-j);
        }
    }
    cout<<dp[n]<<endl;
}