题意：有一棵n个点的形态不定的树，每个度为i的节点会使树的权值增加f[i]，求树的最大权值
n<=2015，0<=f[i]<=1e4
思路：对不起队友，我再强一点就能赛中出这题了
显然每个点的度至少为1，且度数为1的节点至少有2个（From 队友）
有一个结论：给每个点都分配1个度，剩余的度任意分配，一定能构造出对应的方案
仔细想想题面里的生成树数量不就在暗示我有类似Prufer序的性质么……序列与构造一一对应……唉太菜了
然后就是经典的完全背包问题了
每个点分配一个度之后还剩余n-2个度，每个点的分配到1之后多出来的度是[0,n-2]
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<ctime> 6 #include<cmath> 7 #include<algorithm> 8 #include<iomanip> 9 #include<vector> 10 #include<map> 11 #include<set> 12 #include<bitset> 13 #include<queue> 14 #include<stack> 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned int uint; 18 typedef unsigned long long ull; 19 typedef pair<int,int> PII; 20 typedef vector<int> VI; 21 #define fi first 22 #define se second 23 #define MP make_pair 24 #define N 2100 25 #define M 110000 26 #define eps 1e-8 27 #define pi acos(-1) 28 #define oo 1000000000 29 #define MOD 10007 30 31 int a[N],f[N],dp[N]; 32 33 34 int main() 35 { 36 //freopen("hdoj5534.in","r",stdin); 37 //freopen("hdoj5534.out","w",stdout); 38 int cas; 39 scanf("%d",&cas); 40 for(int v=1;v<=cas;v++) 41 { 42 int n; 43 scanf("%d",&n); 44 for(int i=1;i<n;i++) scanf("%d",&a[i]); 45 for(int i=1;i<n;i++) f[i-1]=a[i]-a[1]; 46 int m=n-2; 47 memset(dp,0,sizeof(dp)); 48 dp[0]=n*a[1]; 49 for(int i=1;i<=m;i++) 50 for(int j=1;j<=i;j++) dp[i]=max(dp[i],dp[i-j]+f[j]); 51 printf("%d ",dp[m]); 52 } 53 return 0; 54 } 55 56