写的不好！计划重写一篇。
树形背包博大精深！
绝对不咕！
树形分组背包
【例题】 选课 *luogu-p2014 *
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
【分析】
记录状态：$f[u][i]$为以$u$为根的子树上，选择$i$门课所能获得的最大学分。
记$u$为当前正在处理的结点，$v$为刚刚递归访问结束的结点。那么在$u$上相当于有一个容量为$M$的背包，每个子树中不同的状态相当于不同的物品，例如$f[v][j]$为体积为$j$，价值为$f[v][j]$中存储的数值。
在本题中，由于所有关系构成森林结构，因此可以设$0$号结点为“没有先修课”的课的先修课。然后以$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
| #include<bits/stdc++.h>
using namespace std;
#define Pb push_back
const int MAXN=305;
const int MAXM=305;
int N,M;
vector<int> son[MAXN];
int a[MAXN],f[MAXN][MAXM];
inline void dp(int u)
{
for(vector<int>::iterator it=son[u].begin();it!=son[u].end();it++)
{
int v=*it;
dp(v);
for(register int i=M;i>=0;--i)
for(register int j=0;j<=i;++j)
f[u][i]=max(f[u][i],f[u][i-j]+f[v][j]);
}
if(u)
{
for(register int i=M;i>=1;--i)
f[u][i]=f[u][i-1]+a[u];
}
}
int main()
{
scanf("%d%d",&N,&M);
for(register int i=1;i<=N;++i)
{
int k,s;
scanf("%d%d",&k,&s);
son[k].Pb(i);a[i]=s;
}
dp(0);
printf("%d",f[0][M]);
return 0;
}
|
【例题】有线电视网 luogu-p1273
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
【分析】
记录状态：$f[i][j]$为以$i$为根，选择$j$个用户最多有多少收入。状态转移时如果无法从正面入手（如本题不知道价格的最值，且价值分布更为稀疏），可以从反面设计状态，在输出答案时进行判断即可。转移时可以记录$size$数组进行优化。
【代码】
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>
using namespace std;
struct Edge{
int v,w,nxt;
}mem[3005*2];
int head[3005],cnt;
int size[3005];
inline void AddEdge(int u,int v,int w){
mem[++cnt].v=v;
mem[cnt].w=w;
mem[cnt].nxt=head[u];
head[u]=cnt;
}
int N,M;
int leaf[3005];
int f[3005][3005];
inline void dfs(int u){
if(leaf[u]){
f[u][1]=leaf[u];
size[u]=1;
return;
}
for(register int i=head[u];i;i=mem[i].nxt){
int v=mem[i].v,w=mem[i].w;
dfs(v);
size[u]+=size[v];
for(register int j=M;j>=1;--j)
for(register int k=0;k<=min(size[v],j);++k)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w);
}
}
int main(){
memset(f,0xcf,sizeof(f));
scanf("%d%d",&N,&M);
for(register int i=1;i<=N-M;++i){
int k;
scanf("%d",&k);
for(register int j=1;j<=k;++j){
int a,c;
scanf("%d%d",&a,&c);
AddEdge(i,a,c);
}
}
for(register int i=1;i<=M;++i) scanf("%d",&leaf[N-M+i]);
for(register int i=1;i<=N;++i) f[i][0]=0;
dfs(1);
for(register int i=M;i>=1;--i){
if(f[1][i]>=0){
printf("%d",i);
return 0;
}
}
return 0;
}
|
组合计数类树形背包
【例题】树的独立集 （原创）
给定一棵有$N$个结点的树，输出这棵树中包含$K$个结点的独立集个数。
【分析】
有关组合计数的背包类树形dp问题，一般均可用以下方式解决。
记录状态：$f[u][k][0/1]$ 为以$u$为根的子树，$u$的状态为选或不选，共选择$k$个结点时独立集的个数。
记$u$为当前正在处理的结点，$v$为刚刚递归访问结束的结点。每递归访问结束一个子结点，就考虑把该子结点的状态与已经处理一部分的当前结点状态相匹配。每访问完一个结点，就把配对后产生的状态归为已处理的状态。由于需要根据之前的状态推导后续状态，因此不难看出利用到背包的思想。
状态转移方程的基本思想如下：
$$
f[u][i+j][(state)]=combine(f[u][i][(state)]*f[u][j][(state)])
$$
本题的状态转移方程也不难推出：
$$
f[u][0][i+j]=\sum f[u][0][i]*(f[v][0][j]+f[v][1][j])
$$
$$
f[u][1][i+j]=\sum f[u][1][i]*f[v][0][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
41
42
43
44
45
| #include<bits/stdc++.h>
using namespace std;
const int MAXN=10005;
int N,K;
vector<int> G[MAXN];
int f[MAXN][105][2];
int g[105][2];
int size[MAXN];
void dp(int fa,int u){
size[u]=1;
f[u][0][0]=1,f[u][1][1]=1;
for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++){
int v=*it;
if(v==fa) continue;
dp(u,v);
for(register int i=0;i<=min(K,size[u]);++i){
g[i][0]=f[u][i][0],f[u][i][0]=0;
g[i][1]=f[u][i][1],f[u][i][1]=0;
}
for(register int i=0;i<=min(K,size[u]);++i){
for(register int j=0;j<=min(K-i,size[v]);++j){
f[u][i+j][0]+=g[i][0]*(f[v][j][0]+f[v][j][1]);
f[u][i+j][1]+=g[i][1]*f[v][j][0];
}
}
size[u]+=size[v];
}
}
int main(){
scanf("%d%d",&N,&K);
for(register int i=1;i<N;++i){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dp(0,1);
printf("%d",f[1][K][0]+f[1][K][1]);
return 0;
}
|
习题
潜入行动
未完待续~