Fork me on GitHub

树形DP小结

我真的菜死了啊/(ㄒoㄒ)/~~

没有上司的舞会

传送门
首先一个显然的状态就是一个节点和他的父亲节点不能同时被选中,又因为我们进行树形$DP$的时候合并是以每个点为根的子树合并,所以只能从下向上合并.
所以我们设$f_{i,j}$表示以$i$为根的节点,其中$j$代表这个节点的子节点选了/没选时,最多的欢乐值是多少.
那么转移的时候,我们枚举每个非叶节点的子节点$k$,然后转移比较显然.

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
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define ll long long
#define MP make_pair
#define max(a,b) (a>b)?a:b
#define F(i,a,b) for(int i=a;i<=b;i++)
#define D(i,a,b) for(int i=a;i>=b;i--)
#define PB push_back

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

const int N = 6005;

int n , t , root;
int val[N] , degree[N] , head[N];
int f[N][2];

struct Edge {
int to;
int next;
}e[N << 2];

inline void add ( int x , int y ) {
e[++t].to = y;
e[t].next = head[x];
head[x] = t;
return;
}

void dfs ( int x , int fa ) {
f[x][0] = 0;
f[x][1] = val[x];
for ( int i = head[x] ; i ; i = e[i].next ) {
int y = e[i].to;
if ( y == fa )
continue;
dfs ( y , x );
f[x][0] += max ( f[y][0] , f[y][1] );
f[x][1] += f[y][0];
}
return;
}

int main ( void ) {
n = read ();
F ( i , 1 , n )
val[i] = read ();
int x = read () , y = read ();
while ( x && y ) {
add ( y , x );
degree[x]++;
x = read () , y = read ();
}
F ( i , 1 , n )
if ( !degree[i] ) {
root = i;
break;
}
dfs ( root , 0 );
printf ( "%d\n" , max ( f[root][0] , f[root][1] ) );
return 0;
}

computer

传送门
发现这个东西可以在求直径的时候顺便求出来,所以这道题等价于用$DP$求一遍树的直径…..
然后我们来重点剖析一下怎么用$DP$的方法去求树的直径.
我们设$f_{x,0}$表示在$x$这颗子树中,由$x$向下最长能延申的距离是多少.同时我们再设$f_{x,1}$表示在$x$这颗子树中,由$x$向下走次长的链的长度为多少.
但是发现我们还需要解决在$x$的子树中最长的链不经过$x$的情况,所以我们设$f_{x,2}$表示$x$通过它的父亲最长能向上延申多少距离.
不难发现,前两个$f$数组可以在一次从下向上的$dfs$中求出,而第三个$f$数组则单独需要一个从上向下的$dfs$求出.
那么对于某个$f_{x,2}$,转移方程有$f_{y,2}=max(f_{x,2},f_{y,0}+e_i.date==f_{x,0}?f_{x,1}:f_{x,0})+e_i.date$

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
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;

int n , t;
int head[N] , f[N][3];
struct Edge {
int to;
int date;
int next;
}e[N << 2];

inline void add ( int x , int y , int z ) {
e[++t].to = y;
e[t].date = z;
e[t].next = head[x];
head[x] = t;
return;
}
void dfs1 ( int x , int fa ) {
for ( int i = head[x] ; i ; i = e[i].next ) {
int y = e[i].to;
if ( y == fa )
continue;
dfs1 ( y , x );
int temp = f[y][0] + e[i].date;
if ( temp >= f[x][0] ) {
f[x][1] = f[x][0];
f[x][0] = temp;
}
else if ( temp > f[x][1] )
f[x][1] = temp;
}
return;
}
void dfs2 ( int x , int fa ) {
for ( int i = head[x] ; i ; i = e[i].next ) {
int y = e[i].to;
if ( f[x][0] == f[y][0] + e[i].date )
f[y][2] = max ( f[x][2] , f[x][1] ) + e[i].date;
else
f[y][2] = max ( f[x][2] , f[x][0] ) + e[i].date;
dfs2 ( y , x );
}
return;
}
int main ( void ) {
while ( scanf ( "%d" , &n ) != EOF ) {
t = 0;
memset ( f , 0 , sizeof ( f ) );
memset ( head , 0 , sizeof ( head ) );
for ( int i = 2 ; i <= n ; i++ ) {
int x , y;
scanf ( "%d%d" , &x , &y );
add ( x , i , y );
}
dfs1 ( 1 , 0 );
dfs2 ( 1 , 0 );
for ( int i = 1 ; i <= n ; i++ )
printf ( "%d\n" , max ( f[i][0] , f[i][2] ) );
}
return 0;
}

最优连通子集

传送门
lok
20年前的Noi题目
题目大意大概为给定一个平面整点集,点与点间在$|x_1-x_2|+|y_1-y_2|=1$时相邻,且形成的图没有回路,每个点有一个可正可负的权值,求最大权和连通子图。
有了题目大意,发现就是给你一颗树.让你在这棵树中选择一个联通的点集,使得这个联通的点集的权值最大,求出这个最大值.
发现显然是个树形背包嘛,我们设$f_{x,j}$表示在以$x$为根的子树中选/不选$x$这个节点时最大的权值和.然后我们可以直接从下往上转移.我们转移的时候发现,如果$i$这个点被选了,那么对于它所有的子树,如果$f_{y,1}$的值大于$0$,那么答案加上这颗子树一定会更优.而在我们转移$f_{x,0}$时,因为$x$这个节点不能选,所以我们就只能去选择这个节点的某一颗子树作为这个$f$的值.
而最后的答案就是$max(f_{root,0},f_{root,1})$.

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int inf = 1<<28;
int n,m;
struct Point{
int x,y,c;
}p[1010];

vector<int> con[1010];
int dp[1010][2],mark[1010];

void dfs(int v){
mark[v]=1;
dp[v][0]=0,dp[v][1]=p[v].c;
int j;
for (int i=0;i<con[v].size();i++)
if (!mark[con[v][i]]){
j=con[v][i];
dfs(j);
dp[v][0]=max(dp[v][0],max(dp[j][0],dp[j][1]));
if (dp[j][1]>0) dp[v][1]+=dp[j][1];
}
return;
}

int main ( void ) {
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
if (abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)==1){
con[i].push_back(j);
con[j].push_back(i);
}
dfs(0);
printf("%d\n",max(dp[0][0],dp[0][1]));
return 0;
}

The more, The Better

传送门
tm2
简单背包即可….

选课

传送门
首先一个思路就是我们设$f_{i,j,0 \vert 1}$来表示以$i$为根节点的子树中,选择了$j$个物品,其中$i$选/不选时最大的价值.
但是我们发现如果$i$不能选,那么$i$这颗子树一定就不能选,第三维没有什么必要,所以我们强制初始时$f_{i,1}=v_i$,然后转移的时候,用类似背包的思路.即枚举容量即可.

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
55
56
57
58
59
#include <bits/stdc++.h>
#define ll long long
#define MP make_pair
#define max(a,b) ( a > b ) ? a : b
#define F(i,a,b) for(int i=a;i<=b;i++)
#define D(i,a,b) for(int i=a;i>=b;i--)
#define PB push_back

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

const int N = 305;

int n , m , t;
int head[N] , f[N][N] , siz[N];
struct Edge {
int to;
int next;
} e[N << 2];

inline void add ( int x , int y ) {
e[++t].to = y;
e[t].next = head[x];
head[x] = t;
return;
}

void dfs ( int x , int fa ) {
siz[x] = 1;
for ( int i = head[x] ; i ; i = e[i].next ) {
int y = e[i].to;
if ( y == fa )
continue;
dfs ( y , x );
for ( int j = siz[x] ; j ; j-- )
for ( int k = 0 ; k <= siz[y] ; k++ )
f[x][j + k] = max ( f[x][j + k] , f[x][j] + f[y][k] );
siz[x] += siz[y];
}
return;
}

int main ( void ) {
n = read () , m = read ();
F ( i , 1 , n ) {
int fa = read ();
add ( fa , i );
add ( i , fa );
f[i][1] = read ();
}
dfs ( 0 , -1 );
printf ( "%d\n" , f[0][m + 1] );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:树形DP小结

文章作者:KRrrrrrrrr

发布时间:2019年11月10日 - 10:11

最后更新:2019年11月11日 - 10:11

原始链接:http://krrrr.xyz/2019/11/10/树形DP小结/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。