HDU 5534/ 2015长春区域H.Partial Tree DP
Partial Tree
You find a partial tree on the way home. This tree has n
nodes but lacks of n−1
edges. You want to complete this tree by adding n−1
edges. There must be exactly one path between any two nodes after adding. As you know, there are nn−2
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)
, where f
is a predefined function and d
is the degree of this node. What's the maximum coolness of the completed tree?
indicating the total number of test cases.
Each test case starts with an integer n
in one line,
then one line with n−1
integers f(1),f(2),…,f(n−1)
.
1≤T≤2015
2≤n≤2015
0≤f(i)≤10000
There are at most 10
test cases with n>100
.
3
2 1
4
5 1 4
19
#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 ;
}
代码
最新文章
- redis数据类型之—Sorted set
- 高仿淘宝和聚美优品商城详情页实现《IT蓝豹》
- [主页]大牛系列01:Microsoft Research的Johannes Kopf
- JavaScript的条件语句
- 因為 Hypervisor 未執行,所以無法啟動虛擬機器
- 李洪强iOS开发之上传照片时英文改中文
- 流媒体相关知识介绍 及其 RTP 应用
- android recovery模式及ROM制作
- 两次fopen不同的文件返回相同的FILE* 地址
- Android之ExpandableListView的属性(Group不展开)
- Oracle连接数过多释放机制
- IntelliJ IDEA 设置Output (输出窗口)窗口字体大小
- android开发_文本按钮 与 输入框
- React事件绑定与解绑
- μC/OS-II 信号量集
- Assembly.LoadFrom加载程序集类型转换失败解决方法
- Android逆向笔记之AndroidKiller与Android Studio的使用
- ledecode Reverse Words in a String III
- NYOJ 116 士兵杀敌二
- Javascript专题(三)c.各种轮播--上下滚动轮播(面向对象版本)