竞赛讨论区 > D题牛牛种小树
头像
SSDUT_cyq
发布于 2021-09-24 22:35
+ 关注

D题牛牛种小树

我们可以轻松地发现这道题是一道dp的题目

对于整张图来说,总共有2*n-2地度数,由于每一个点都至少有一个度数,我们就只剩下n-2的度数可以进行自由分配

我们将每个点看做一个点加上一条没有连上其他点的边,然后在更新的时候将所有点联向当前树的叶子节点上,然后根据其度数做一下背包就好了

f[i] 表示树上已经有i 个点的最佳权值

假设度数为i的贡献为a[i],当一个节点插入的时候,会损失a[1]的价值,增加a[i-j+1]的价值,所以转移方程为

f[i]=max(f[i],f[j]+a[i-j+1]-a[1]),1<=j<=i;

然后直接转移即可
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define LL long long
const int MAXN=1e4+7;
const LL INF=1e18;
LL f[MAXN];
int a[MAXN];
int main()
{


    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0x80,sizeof f);
        int cnt=0;
        int x=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d",a+i);
        }
        f[0]=0;
        for(int i=1;i<=n-1;i++)
        {
            for(int j=i;j<=n-2;j++)
            {
                f[j]=std::max(f[j],f[j-i]+1ll*a[i+1]-a[1]);
            }
        }
        LL ans=f[n-2]+1ll*n*a[1];
        std::cout<<ans<<std::endl;

    }

    return 0;
}


全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐