HDU - 5534 Partial Tree(每种都装的完全背包)
Partial Tree
You find a partial tree on the way home. This tree has nn nodes but lacks of n−1n−1 edges. You want to complete this tree by adding n−1n−1edges. There must be exactly one path between any two nodes after adding. As you know, there are nn−2nn−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)f(d), where ff is a predefined function and dd is the degree of this node. What's the maximum coolness of the completed tree?
InputThe first line contains an integer TT indicating the total number of test cases.
Each test case starts with an integer nn in one line,
then one line with n−1n−1 integers f(1),f(2),…,f(n−1)f(1),f(2),…,f(n−1).
1≤T≤20151≤T≤2015
2≤n≤20152≤n≤2015
0≤f(i)≤100000≤f(i)≤10000
There are at most 1010 test cases with n>100n>100.OutputFor 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 因为每种装的范围为【1,+无穷】,然而分组背包的三次方会T,所以要想办法将其转化为完全背包模型。
因为每个点都至少有一度,所以我们预先放入n个一度,本来要放的2×n-2度现在只剩n-2度。
每当再次放入一个x度时,他的贡献为x-1度,在放入的同时减掉之前预先放好的一度。这样便保证了每个点至少有一度。
#include<bits/stdc++.h>
#define MAX 2018
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll; int a[MAX];
ll dp[MAX]; int main()
{
int t,n,m,i,j,k;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=;i<n;i++){
scanf("%d",&a[i]);
}
memset(dp,-INF,sizeof(dp));
dp[]=;
for(i=;i<n;i++){
for(j=i-;j<=n-;j++){
dp[j]=max(dp[j],dp[j-(i-)]+a[i]-a[]);
}
}
printf("%I64d\n",dp[n-]+n*a[]);
}
return ;
}
最新文章
- Spring Security(08)——intercept-url配置
- BestCoder Round #53 (div.1)
- SharePoint 2010 常用技巧及方法总结
- LeetCode 326 Power of Three
- XmlWriter/XmlReader示例代码
- Python 初学笔记(转)
- Java 网络编程 字符流的发送与接收 自定义数据边界
- 只有有lua编译能力不足200K代码吧?NO! Python 有可能。
- Centos中压缩(zip)和解压(unzip)命令
- UVa1587 盒子
- 团队作业4——第一次项目冲刺(Alpha版本) Day 1
- NodeJS跨域问题
- padding和margin
- ZOJ 2477 Magic&#160;Cube(魔方)
- 前端框架之Vue(6)-列表渲染
- P4137 Rmq Problem / mex
- jdbc读取百万条数据出现内存溢出的解决办法
- koa2学习笔记02 - 给koa2添加系统日志 —— node日志管理模块log4js
- Diabetic Retinopathy Winner&#39;s Interview: 1st place, Ben Graham
- NLP十大里程碑