题意:给出你n个节点,请添加n-1条边使得它变成一棵树。这个树必须足够“酷”,每个节点的“酷”值的定义为对于一个度数为x的节点,那么它的一个价值为f(x),求所有节点最大的酷值和。


题解:dp好题。假设我们考虑到每个点还剩多少度这样分配,那么时间复杂度为O(n3),明显GG,于是我们考虑将每个点预先分配一度,由于总度数是2n-2,那么就剩下n-2度需要分配。于是我们可以将其他度数的f值变成与度数为1的f值的差值。这样只需要考虑n-2个度数的分配,于是转化为完全背包,时间复杂度为O(n2)。(freeloop还是神啊,一听题意就瞬间给出每个点分配一个度的方案,但是最后都纠结于O(n3)的复杂度,完全没想到无意中已经降了一层,真的是非常有意思了)


代码:

StatusAccepted
Time78ms
Memory1700kB
Length605
LangG++


#include <bits/stdc++.h>
using namespace std;
const int maxn=3000;
const int inf=0x3f3f3f3f;
int n, T;
int f[maxn], dp[maxn];
int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i=1;i<n;i++)scanf("%d", &f[i]);
        int ans=f[1]*n;
        for(int i=0;i<n-1;i++)f[i]=f[i+1]-ans/n;
        for(int i=0;i<n;i++)dp[i]=-inf;
        dp[0]=0;
        for(int i=1;i<=n-2;i++){    //分配的度数
            for(int j=0;j+i<=n-2;j++){  //上一个状态
                dp[j+i]=max(dp[j+i], dp[j]+f[i]);
            }
        }
        printf("%d\n", ans+dp[n-2]);
    }
    return 0;
}