树形动态规划（最大子独立集）
最大子独立集
对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）。
- 1
- 2
输入
第1行：1个整数N(1 <= N <= 6000)，表示树的结点个数，树中结点的编号从1..N
接下来N-1行，每行2个整数u，v，表示树中的一条边连接结点u和v
- 1
- 2
- 3
输出
第1行：1个整数，表示最大独立集的结点个数
- 1
- 2
样例输入
11
1 2
1 3
3 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
样例输出
7
- 1
- 2
分析
这一题是学习树形DP的基础，要求掌握，题目本身不难，只是树形DP入门。
由题意可知，当我们选择一个点时，就不能选择与它相邻的。所以这个点分为选与不选两种状态。
所以定义状态Dp[i][1]（选择i点的最优解）,Dp[i][0](不选i点的最优解)。
最后的解就是Dp[root][1]与Dp[root][0]中大的那个，root是根节点。
可能会问：题目不是说无根树吗？
对，这里是无根树，但由于算法需求，我们先转成有根数，即随便找一个点当根（此后，就一直以它为根）。
在学习树形Dp的阶段，会遇到很多需要无根转有根的。
废话就不多说了，接下来看状态转移方程。
想一想，Dp[i][1]能从什么状态转过来，
这很好想，既然i这个点选了，那它儿子就不选呀。
所以Dp[i][1]+=Dp[v][0]; 其中，v是儿子编号，至于‘+=’嘛，因为答案是叫求和。
那Dp[i][0]呢？
i选了，它儿子必须选吗？
所以Dp[i][0]+=max(Dp[v][0],Dp[v][1]);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
下面给出完整代码（注释)
差点忘了，还有输入
题目只是说两边相连，但并没有说谁是父亲。
所以我们用一个动态数组存点的儿子
所以输入点x，y时
就把x的儿子存成y
y的儿子存成x
在求解时，函数传参时维护一个父亲，
只需判断儿子是不是父亲即可。
下面是完整代码
Code
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
int n;
int Dp[6005][2];//状态
vector<int>G[6005];//儿子
void Tdp(int x,int fa){
Dp[x][1]=1;//因为每个点都算一个，即使是叶节点
for(int i=0;i<G[x].size();i++){//枚举儿子
int v=G[x][i];//简化程序
if(v==fa)continue;//儿子等于父亲
Tdp(v,x);//递归求解，先计算下层的节点（想想为什么）
Dp[x][1]+=Dp[v][0];
Dp[x][0]+=max(Dp[v][0],Dp[v][1]);//转移
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);//存入数组
}
Tdp(1,0);//把1号当成根，由于题目中没有0号节点，所以父亲为0（最好为-1）
printf("%d",max(Dp[1][0],Dp[1][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
要利用好基础解决更多问题
接下来看一道复杂一点的题
题目描述
Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。
- 1
- 2
输入
第一行一个整数N。(1≤N≤6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
- 1
- 2
- 3
- 4
输出
第1行：输出最大的快乐指数。
- 1
- 2
样例输入
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
样例输出
5
- 1
- 2
思路基本一样，下面给出代码
#include<cstdio>
#include<vector>
using namespace std;
int n,rt;
int Dp[6005][2],hap[6005];//hap为开心值
vector<int>G[6005];//儿子
int F[6005];//存父亲
void Tdp(int x){
Dp[x][1]=hap[x];//不知你有没有发现，之前的1变成了各自的开心值
for(int i=0;i<G[x].size();i++){//由于知道根，关系固定，所以不用判断，
int v=G[x][i];
Tdp(v);
Dp[x][1]+=Dp[v][0];
Dp[x][0]+=max(Dp[v][0],Dp[v][1]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&hap[i]);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
F[x]=y;//存父亲
G[y].push_back(x);
}
for(int i=1;i<=n;i++)//多了一个找根的过程
if(!F[i]){rt=i;break;}
Tdp(rt);
printf("%d",max(Dp[rt][0],Dp[rt][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
有时候，这种题会结合其它知识，看一道吧
题目描述
你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。
给定N个人(姓名，他参加聚会的欢乐指数，以及他上司的名字)，编程找到能使欢乐指数之和最大的若干个人。
- 1
- 2
- 3
输入
第一行一个整数N(N＜100)。
接下来有N行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过20的字符串，欢乐指数是在0到100之间的整数。
- 1
- 2
- 3
输出
第1行：所邀请的人最大的欢乐指数之和
- 1
- 2
样例输入
5
BART 1 HOMER
HOMER 2 MONTGOMERY
MONTGOMERY 1 NOBODY
LISA 3 HOMER
SMITHERS 4 MONTGOMERY
- 1
- 2
- 3
- 4
- 5
- 6
- 7
样例输出
8
- 1
- 2
是不是很熟悉，但这一题存在一个问题，读入不在是编号，而是字符串，这该怎么办呢？
如果学过的同学应该会想到，如何把字符串和编号联系起来。
对，用map（关联式容器）又叫映射
在代码中解释
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define MAXN 100
int n,rt;
int Dp[MAXN+5][2],H[MAXN+5],F[MAXN+5];//H为开心值，F为父亲编号
vector<int>G[MAXN+5];//儿子
map<string,int>N;//字符串对应编号
map<int,string>FF;//编号对应父亲的字符串
void Tdp(int x){//函数一样，主要多一个转化
Dp[x][1]=H[x];
Dp[x][0]=0;
for(int i=0;i<G[x].size();i++){
int v=G[x][i];
Tdp(v);
Dp[x][1]+=Dp[v][0];
Dp[x][0]+=max(Dp[v][0],Dp[v][1]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
string x,y; int z;
cin>>x;scanf("%d",&z);cin>>y;//读入
N[x]=i; FF[i]=y; H[i]=z;
//map就是这么666，可以把字符串、负数等当下标
}
for(int i=1;i<=n;i++){//开始转化编号
F[i]=N[FF[i]];
G[F[i]].push_back(i);
if(!F[i])rt=i;
}
Tdp(rt);
printf("%d",max(Dp[rt][0],Dp[rt][1]));
}
