uva 11782 Optimal Cut

本文从WordPress迁移而来, 查看全部WordPress迁移文章

【重做DP系列】树DP

题意:首先解释一下题目说的cut,一个cut就是在树中选出一些点,能覆盖掉所有根到叶子的路径,并且一条路径上只能出现一个选中的节点,什么意思?看题目中的图片

灰色的7,覆盖了它下面的4条路径,即根去到叶子10,10,0,0的路径都经过7,所以7覆盖了这4条路径,并且在这4条路径内,只有7这个点被选中

灰色的4,覆盖了它下面的2条路径,即根去到叶子8,-5的路径都经过4,并且这2条路径内只有4这个点被选中

灰色0,3,已经是叶子,它们覆盖了它们各自的路径,同样在这2条路径里只有它被选中
因而这4个灰点覆盖了所有的路径

给出一棵满二叉树的深度H(题目说a complete binary tree,实际上不是完全二叉树,都是满二叉树来的),和一个限制值K,然后给出树节点的权值,权值的顺序按照前序遍历的顺序给出。选出小于等于K个节点,使它们组成一组cut,并使这个cut的权值和最大(注意不一定选够K个节点,不超过K个即可)

cut中要满足一个条件,一条路径上不能出现2个或以上被选中的点,这个限制条件要怎么满足?思考就可以知道,实际意思就是,如果一个节点被选入了cut,那么它的子孙后代都不能选,否则必有某些路径上出现2个被选中的点。另外一个条件,一定要覆盖完所有路径,那么如果一个节点不选,要怎么办?那么它的左右孩子一定要同时选上!(同样的,如果有一个孩子也不选,那么这个孩子的两个孩子也一定要被选上!是一个递推下去的过程),因为要选小于等于K个的时候,实际上就是把这K个任务分摊下去给它的子孙后代

状态转移方程:

dp[rt][m]表示在以rt为节点的子树里,选出小于等于K个节点组成的权和最大值,目标状态为dp[1][K]

dp[rt][m] = max{ dp[rt][1] , dp[lch][i] + dp[rch][m-i] } (其中dp[rt][i]实际就是rt该节点的权值)

dp[rt][1] = w[rt],在rt这个子树选1个点,实际上只能选rt自己,并且一定要选,否则不能覆盖全部路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1050010
#define M 25
#define INF 10000000010
#define cl memset
#define lch(i) ((i)<<1)
#define rch(i) ((i)<<1|1)

int H,K,a[N],__pow[M];
struct node{
int w,dep;
}t[N];
bool vis[N][M];
int dp[N][M];

void build(int rt,int dep){
if(dep > H) return ;
scanf("%d",&t[rt].w);
t[rt].dep = dep;
build(lch(rt),dep+1);
build(rch(rt),dep+1);
}

void dfs(int rt,int m){
if(vis[rt][m]) return ;
vis[rt][m] = true;
dp[rt][m] = t[rt].w;
if(t[rt].dep == H || m == 1) return ;
for(int i = 1; i < m ; i++){
dfs(lch(rt),i);
dfs(rch(rt),m-i);
if(dp[lch(rt)][i] + dp[rch(rt)][m-i] > dp[rt][m])
dp[rt][m] = dp[lch(rt)][i] + dp[rch(rt)][m-i];
}
}

int main(){
for(int i = 0; i <= 21; i++) __pow[i] = 1 << i;
while(scanf("%d",&H)!=EOF && H >= 0){
scanf("%d",&K);
build(1,0);
//for(int i = 1; i < __pow[H+1]; i++)
//printf("%d %d\n",t[i].w,t[i].dep);
for(int i = 0; i <= __pow[H+1]+10; i++)
for(int j = 0; j <= K + 3; j++)
vis[i][j] = false;
dfs(1,K);
printf("%d\n",dp[1][K]);
}
return 0;
}