最大子独立集

对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）。

输入

第1行：1个整数N(1 <= N <= 6000)，表示树的结点个数，树中结点的编号从1..N

接下来N-1行，每行2个整数u，v，表示树中的一条边连接结点u和v

输出

第1行：1个整数，表示最大独立集的结点个数

样例输入

1 2

1 3

3 4

3 5

3 6

4 7

4 8

5 9

5 10

6 11

样例输出

分析

这一题是学习树形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]);

下面给出完整代码（注释)

差点忘了，还有输入

题目只是说两边相连，但并没有说谁是父亲。

所以我们用一个动态数组存点的儿子

所以输入点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]));//最优解

}

要利用好基础解决更多问题

接下来看一道复杂一点的题

题目描述

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。

输入

第一行一个整数N。(1≤N≤6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

输出

第1行：输出最大的快乐指数。

样例输入

1 3

2 3

6 4

7 4

4 5

3 5

样例输出

思路基本一样，下面给出代码

#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]));

}

有时候，这种题会结合其它知识，看一道吧

题目描述

你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。

给定N个人(姓名，他参加聚会的欢乐指数，以及他上司的名字)，编程找到能使欢乐指数之和最大的若干个人。

输入

第一行一个整数N(N＜100)。

接下来有N行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过20的字符串，欢乐指数是在0到100之间的整数。

输出

第1行：所邀请的人最大的欢乐指数之和

样例输入

BART 1 HOMER

HOMER 2 MONTGOMERY

MONTGOMERY 1 NOBODY

LISA 3 HOMER

SMITHERS 4 MONTGOMERY

样例输出

是不是很熟悉，但这一题存在一个问题，读入不在是编号，而是字符串，这该怎么办呢？

如果学过的同学应该会想到，如何把字符串和编号联系起来。

对，用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]));

}

树形动态规划（最大子独立集）

树形动态规划（最大子独立集）

最大子独立集

题目描述

题目描述

相关推荐