HDU 5534/ 2015长春区域H.Partial Tree DP

Partial Tree

Problem Description
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two nodes are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

You find a partial tree on the way home. This tree has nHDU 5534/ 2015长春区域H.Partial Tree    DP

nodes but lacks of n−1HDU 5534/ 2015长春区域H.Partial Tree    DP

edges. You want to complete this tree by adding n−1HDU 5534/ 2015长春区域H.Partial Tree    DP

edges. There must be exactly one path between any two nodes after adding. As you know, there are nHDU 5534/ 2015长春区域H.Partial Tree    DPn−2HDU 5534/ 2015长春区域H.Partial Tree    DPHDU 5534/ 2015长春区域H.Partial Tree    DP

ways to complete this tree, and you want to make the completed tree as cool as possible. The coolness of a tree is the sum of coolness of its nodes. The coolness of a node is f(d)HDU 5534/ 2015长春区域H.Partial Tree    DP

, where fHDU 5534/ 2015长春区域H.Partial Tree    DP

is a predefined function and dHDU 5534/ 2015长春区域H.Partial Tree    DP

is the degree of this node. What's the maximum coolness of the completed tree?

 
Input
The first line contains an integer THDU 5534/ 2015长春区域H.Partial Tree    DP

indicating the total number of test cases.
Each test case starts with an integer nHDU 5534/ 2015长春区域H.Partial Tree    DP

in one line,
then one line with n−1HDU 5534/ 2015长春区域H.Partial Tree    DP

integers f(1),f(2),…,f(n−1)HDU 5534/ 2015长春区域H.Partial Tree    DP

.

1≤T≤2015HDU 5534/ 2015长春区域H.Partial Tree    DP

2≤n≤2015HDU 5534/ 2015长春区域H.Partial Tree    DP

0≤f(i)≤10000HDU 5534/ 2015长春区域H.Partial Tree    DP

There are at most 10HDU 5534/ 2015长春区域H.Partial Tree    DP

test cases with n>100HDU 5534/ 2015长春区域H.Partial Tree    DP

.

 
Output
For each test case, please output the maximum coolness of the completed tree in one line.
 
Sample Input
2
3
2 1
4
5 1 4
 
Sample Output
5
19
 
题意:给你n个点,给你1到n-1的度数的价值,让你构造一棵树这颗树的价值就是,度数代表的价值和,问最大是多少,
 
题解:首先度的总和为2(n-1),并且每个节点度不为0。如果用二维dp[i][j]表示第i个节点还剩j个度的最优值,是没问题,但是复杂度为o(n3)。但是其实每个节点都要分配一个度,那么我们先给每个节点分配一个度,剩下n-2的度分给n个点,可以减掉一维,dp[i]表示i个度的最优值,因为度的个数是严格小于节点个数的。背包转移的权值为val[i]-val[1](可能有负数)
 
#include<cstdio>
using namespace std ;
#define inf 1000000
int main(){
int dp[],a,b,n,i,T,j;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&a);
for( i=;i<n;i++){dp[i]=-inf;}
for( i=;i<n;i++){
scanf("%d",&b);b=b-a;
for( j=i-;j<=n-;j++){
if(dp[j-(i-)]+b>dp[j])
dp[j]=dp[j-(i-)]+b;
}
}
printf("%d\n",n*a+dp[n-]);
}
return ;
}

代码

上一篇:HDU 5531 Rebuild (2015长春现场赛,计算几何+三分法)


下一篇:centos7使用docker部署gitlab-ce-zh应用