题意:给出你n个节点,请添加n-1条边使得它变成一棵树。这个树必须足够“酷”,每个节点的“酷”值的定义为对于一个度数为x的节点,那么它的一个价值为f(x),求所有节点最大的酷值和。
题解:dp好题。假设我们考虑到每个点还剩多少度这样分配,那么时间复杂度为O(n3),明显GG,于是我们考虑将每个点预先分配一度,由于总度数是2n-2,那么就剩下n-2度需要分配。于是我们可以将其他度数的f值变成与度数为1的f值的差值。这样只需要考虑n-2个度数的分配,于是转化为完全背包,时间复杂度为O(n2)。(freeloop还是神啊,一听题意就瞬间给出每个点分配一个度的方案,但是最后都纠结于O(n3)的复杂度,完全没想到无意中已经降了一层,真的是非常有意思了)
代码:
Status | Accepted |
---|---|
Time | 78ms |
Memory | 1700kB |
Length | 605 |
Lang | G++ |
#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; }