洛谷树形dp复习

96 阅读 0 评论 64 点赞

我是靠谱客的博主高兴紫菜，这篇文章主要介绍洛谷树形dp复习，现在分享给大家，希望可以做个参考。

P2015 二叉苹果树

明显是树上背包问题，选与不选，保留的树枝为体积，每个树枝的苹果树目为价值

f [ i ] [ j ] 表示在 i 节点时，留下了 j 条树枝时得到的最多苹果数量
模板
枚举孩子节点
·····搜索更新孩子节点信息
·····枚举 i 点树枝数量
············枚举孩子节点所拥有树枝数量
··················状态转移方程
状态转移方程：
f [ u ] [ j ] = max ( f [ u ] [ j ] , f [ u ] [ j - k ] + f [ v ] [ 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
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v,next;
}e[105];
int fa[105],n,m,cnt,head[105],f[105][3000050];
void add(int u,int v)
{
cnt++;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u)
{
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
dfs(v);
for (int j=m+1;j>=1;j--)
for (int k=1;k<j;k++)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
}
int main()
{
scanf("%d %d",&n,&m);
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
if (fa[y])
swap(x,y);
scanf("%d",&f[y][1]);//初始化
fa[y]=x;
add(x,y);//加边
}
for (int i=1;i<=n;i++)
if (!fa[i])
{
dfs(i);
printf("%d",f[i][m+1]);
break;
}
return 0;
}

P2014 [CTSC1997]选课

更上题差不多，树形背包板子题，要注意当我们规定所有树的根统一为0，所选总科目应该为m+1，0节点的科目没有的分，所以不影响答案

复制代码

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
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v,next;
}e[305];
int cnt,f[305][6005],head[305],n,m;
int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void add(int u,int v)
{
cnt++;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u)
{
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
dfs(v);
for (int j=m+1;j>=1;j--)
for (int k=1;k<j;k++)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++)
{
int a=read();
f[i][1]=read();
add(a,i);
}
dfs(0);//约定以0为根进行树上dp
printf("%d",f[0][m+1]);
return 0;
}

P1273 有线电视网

类似的树形背包
f [ i ] [ j ] 表示在 i 节点选择 j 个人时的最大利润
初始化：叶子节点 f [ i ] [ 1 ] = val [ i ]
接着就是纯真无邪的树上背包了。

结果T4个点，对于这个题，我们可以：
!!!减掉无用转移!!!
对于每个节点，它并不是能够选取到所有的人（因为它子树的叶子节点并不一定会包括所有的叶子节点），所以说我们在搜索所有的子树时，都应该返回该子树所包含的叶子节点，然后对 j 进行优化枚举，减少转移次数，然后AC

复制代码

#include <bits/stdc++.h>
#define rg register
using namespace std;
const int minn=-1e7;
struct edge
{
int v,w,next;
}e[10105];
int cnt,n,m,val[3005],f[3005][3005],head[3005];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int u,int v,int w)
{
cnt++;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline int dfs(int u)
{
int sum=0;
for (rg int i=head[u];i;i=e[i].next)
{
int v=e[i].v,w=e[i].w;
sum+=dfs(v);
for (rg int j=sum;j>=0;j--)
for (rg int k=0;k<=j;k++)
{
//printf("f[%d][%d]=%d f[%d][%d]=%d f[%d][%d]=%d
",u,j,f[u][j],u,j-k,f[u][j-k],v,k,f[v][k]);
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w);
//printf("f[%d][%d]=%dn",u,j,f[u][j]);
}
}
return sum+(val[u]?1:0);
}
int main()
{
//freopen("P1273.out","w",stdout);
n=read(),m=read();
for (rg int i=1;i<=n-m;i++)
{
int k=read();
for (rg int j=1;j<=k;j++)
{
int a=read(),c=read();
add(i,a,c);
}
}
for (rg int i=1;i<=n;i++)
for (rg int j=1;j<=m;j++)
f[i][j]=minn;
for (rg int i=n-m+1;i<=n;i++)
f[i][1]=val[i]=read();
dfs(1);
int l=1,r=m;
while (l<=r)//小优化
{
int mid=(l+r)>>1;
if (f[1][mid]>=0)
l=mid+1;
else
r=mid-1;
}
if (f[1][r]>=0)
printf("%d",r);
else
printf("%d",0);
return 0;
}

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
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define rg register
using namespace std;
const int minn=-1e7;
struct edge
{
int v,w,next;
}e[10105];
int cnt,n,m,val[3005],f[3005][3005],head[3005];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int u,int v,int w)
{
cnt++;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline int dfs(int u)
{
int sum=0;
for (rg int i=head[u];i;i=e[i].next)
{
int v=e[i].v,w=e[i].w;
sum+=dfs(v);
for (rg int j=sum;j>=0;j--)
for (rg int k=0;k<=j;k++)
{
//printf("f[%d][%d]=%d f[%d][%d]=%d f[%d][%d]=%d
",u,j,f[u][j],u,j-k,f[u][j-k],v,k,f[v][k]);
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w);
//printf("f[%d][%d]=%dn",u,j,f[u][j]);
}
}
return sum+(val[u]?1:0);
}
int main()
{
//freopen("P1273.out","w",stdout);
n=read(),m=read();
for (rg int i=1;i<=n-m;i++)
{
int k=read();
for (rg int j=1;j<=k;j++)
{
int a=read(),c=read();
add(i,a,c);
}
}
for (rg int i=1;i<=n;i++)
for (rg int j=1;j<=m;j++)
f[i][j]=minn;
for (rg int i=n-m+1;i<=n;i++)
f[i][1]=val[i]=read();
dfs(1);
int l=1,r=m;
while (l<=r)//小优化
{
int mid=(l+r)>>1;
if (f[1][mid]>=0)
l=mid+1;
else
r=mid-1;
}
if (f[1][r]>=0)
printf("%d",r);
else
printf("%d",0);
return 0;
}

P1272 重建道路

记得补

复制代码

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
#include <bits/stdc++.h>
using namespace std;
const int inf=1e8;
struct edge
{
int v,next;
}e[160];
int n,p,cnt,root;
int f[155][155],head[155],a[155];
bool bj[155];
void add(int u,int v)
{
cnt++;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int dp(int x)
{
int sum=1;
for (int i=head[x];i;i=e[i].next)
{
int v=e[i].v;
sum+=dp(v);
for (int j=sum;j>=1;j--)
for (int k=1;k<j;k++)
f[x][j]=min(f[x][j],f[x][j-k]+f[v][k]-1);
}
return sum;
}
int main()
{
scanf("%d %d",&n,&p);
for (int i=1;i<n;i++)
{
int I,J;
scanf("%d %d",&I,&J);
add(I,J);
bj[J]=1;
a[I]++;//统计孩子 
}
memset(f,0x3f,sizeof(f));
for (int i=1;i<=n;i++)
{
if (!bj[i])
root=i;
f[i][1]=a[i];
}
dp(root);
int ans=f[root][p];
for (int i=1;i<=n;i++)
if (f[i][p]<ans)ans=f[i][p]+1;
printf("%d",ans);
return 0;
}

P1270 “访问”美术馆

题目的意思是，小偷要从外面进到美术馆，偷完东西后再出美术馆，所以一条边坑定是要走两次的（来回），而警察来了的时候就判定为被抓到，所以当小偷刚好花费 s 时间时，并不能作为最优答案输出（坑）
这一道题主要是建边，以递归的形式建边，根节点为1，因为题目性质，所以一个点度数只为0或2，保证了该美术馆就是一个二叉树，
然后就可以按照题目的意思来存储树
树的左孩子为 i < < 1，右孩子为 i < < 1 | 1
所以接下来dp的时候就应该从1出发

f [ i ] [ j ] 表示在 i 节点剩余 j 分钟能偷到的画的最大数量
注意事项：
s–
存边时直接将边长<<1（来回走）
dp边界，当没有时间或者节点i 所剩时间j已经被更新过时，可以直接结束dp

dp特判：如果该节点有画，那么就花所剩余的时间偷画（在i节点偷到画的数量一定小于等于该节点画的数量）

dp转移方程：
枚举i点左子树所剩余的时间 j
（为保证能逃出去，j < = time - edge [ i ] ）
f [ i ] [ j ] = max ( f [ i ] [ j ] , f [ i <<1] [ j ] , f [ i<<1|1 ] [ time - edge [ i ] - j ]（应为要给自己逃跑的时间，所以右子树所给的时间要再减去这条道路的时间）

复制代码

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
#include <bits/stdc++.h>
using namespace std;
//第i个展室，共花j分钟， 
int s,f[1005][6005],w[1005],edge[1005];
bool bj[1005];
void dfs(int u)
{
bj[u]=1;
int a,b;
scanf("%d %d",&a,&b);
edge[u]=a<<1;
w[u]=b;
if (!b)
{
dfs(u<<1);
dfs(u<<1|1);
}
}
int dp(int u,int time)
{
if (f[u][time]||time==0)return f[u][time];
if (w[u])
return f[u][time]=min(w[u],max(0,(time-edge[u])/5));
for (int i=0;i<=time-edge[u];i++)
{
dp(u<<1,i);
dp(u<<1|1,time-i-edge[u]);
f[u][time]=max(f[u][time],f[u<<1][i]+f[u<<1|1][time-i-edge[u]]);
}
return f[u][time];
}
int main()
{
scanf("%d",&s);
s--;
dfs(1);
printf("%d",dp(1,s));
return 0;
}