题目链接:uva 11782 - Optimal Cut
题目大意:按照前序给出一棵完全树的前序,每个节点的值,现在要求在这棵树上切最多k刀,使得获得的值最大,但是有一个要求,就是对于每颗子树来说,最多切一刀,并且每个叶子节点都要被切掉才行。
解题思路:dp[i][k]表示i节点为根的子树,切k刀后的最大值。每个节点都有左孩子和右孩子之分,对于一个状态dp[i][k],枚举左孩子的刀数t,dp[i][k] = max(dp[i][k], dp[i*2+1][t] + dp[i*2+2][k-t]).并且注意dp[i][k]还可以由dp[i][k-1]得到,因为可以切小于k刀。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = (1<<20)+5;
const int K = 25;
const int INF = 0x3f3f3f3f;
int n, k, dp[N][K];
void buildTree(int u, int d) {
if (d > n)
return;
scanf("%d", &dp[u][1]);
buildTree(u*2+1, d+1);
buildTree(u*2+2, d+1);
}
int solve () {
int t = (1<<(n+1))-2;
for (int i = 2; i <= k; i++) {
for (int j = t; j >= 0; j--) {
int p = j*2+1;
int q = j*2+2;
dp[j][i] = dp[j][i-1];
if (p > t || q > t)
continue;
for (int x = 1; x < i; x++)
dp[j][i] = max(dp[j][i], dp[p][x] + dp[q][i-x]);
}
}
return dp[0][k];
}
int main () {
while (scanf("%d", &n) == 1 && n != -1) {
scanf("%d", &k);
buildTree(0, 0);
printf("%d\n", solve());
}
return 0;
}
分享到:
相关推荐
Patch-based Near-Optimal Image Denoising http://users.soe.ucsc.edu/~priyam/PLOW/download.php
A General, Fast, and Robust Implementation of the Time-Optimal Path.pdf
前端项目-optimal-select,为HTML元素获取高效、健壮的CSS选择器
sgowris2-inverse-optimal-control.zip
relaying is outage-optimal, that is, it is equivalent in outage behavior to the optimal DaF strategy that employs all potential relays. We further show that opportunistic AaF relaying is outage-...
Unit-4-Optimal-Design-机电专业英语-图文课件.ppt
时间最优MPC
一种基于GEO星地协作网络的优化功率分配方案,刘迪,王卫东,卫星移动通信系统需要有效的抗衰落技术来支持其多业务、高速率的需求。协作分集技术利用卫星同一波束内相邻终端节点充当中继,依
自动化 优化理论及应用 Donald E. Kirk-Optimal Control
Multi-sensor optimal information fusion Kalman filter 卡尔曼滤波
是Pareto-optimal tracing in topology optimization的文章,内涵matlab程序,资源比较难找,大家共享学习一下
A new type of Steiner points for computing size-optimal 网格划分的外文文章,国内找不到,难得的。。。
AH, 2007, 127–146HyperLogLog: the analysis of a near-optimal cardinality estimation algorithmPhilippe Flajolet1 and Éric Fusy1 and Olivier Gandouet2 and Frédéric Meunier11Algorithms Project, ...
Optimal Control Theory - An Introduction.(Kirk D. Dover, 2004
所有光滑度阶凸优化的近似最优下界_Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness.pdf
@book{ author = {Anderson, Brian DO and Moore, John B}, title = {Optimal filtering}, publisher = {Prentice-Hall, Inc.}, address = {New Jersey}, year = {1979}, type = {Book} }
OPTIMAL CAPACITOR PLACEMENT ON RADIAL DISTRIBUTION SYSTEMS
control optimal approche HUM
Near-Optimal and Practical Jamming-Resistant Energy-Efficient Cognitive Radio Communications