2015ICPC chanchun HDU 5534 (树形题转换完全背包)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5534

题意：给你n个点，让你加上n-1条边使他变成一棵树，题目首先给你a[1] a[2].....a[n-1]代表度数为多少时的值，然后问你最大值是多少，n-1条边变成一棵树

思路：这个题首先限制了只能用n^2以下的算法，我们看这个题首先给的东西都是与度数有关，我们建造一棵树度数总和肯定是2*（n-1）

我们其实只要把这个度数当作钱，然后购买相应的商品就可以了，但是你可能买相同的边，有些点你就会没买到造成不是一棵树

这个时候我们就有一个前提，保证是一颗树，那么我们怎么弄呢，我们先保证每个点度数初值为1，所以我们还能用的度数就变成了n-2,然后初值设为n*a[1];

我们推导式因为我们初度数为1，所以我们要添加i度的时候，我们应该删掉原来的度数1然后再加上i+1的度数值

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

#include<bits/stdc++.h>

#define mod 1000000007

#define maxn 100005

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

ll n;

ll f[maxn],d[maxn],a[maxn];

int main(){

    int t;

    scanf("%d",&t);

    for(int k=;k<t;k++){

        cin>>n;

        for(int i=;i<=n-;i++) cin>>a[i];

        memset(f,,sizeof(f));

        f[]=n*a[];

        for(int i=;i<=n-;i++){

            for(int j=i-;j<=n-;j++){

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

            }

        }

        printf("%lld\n",f[n-]);

    }

}

巴特西

2015ICPC chanchun HDU 5534 (树形题转换完全背包)

最新文章

热门文章