题目：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=0;k<t;k++){ cin>>n; for(int i=1;i<=n-1;i++) cin>>a[i]; memset(f,0,sizeof(f)); f[0]=n*a[1]; for(int i=2;i<=n-1;i++){ for(int j=i-1;j<=n-2;j++){ f[j]=max(f[j],f[j-i+1]+a[i]-a[1]); } } printf("%lld\n",f[n-2]); } }
2015ICPC chanchun HDU 5534 (树形题转换完全背包)
原文：https://www.cnblogs.com/Lis-/p/10943492.html