文档介绍：该【nwpu2014暑假集训：动态规划4 ——树状dp 】是由【jiqingyong14】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【nwpu2014暑假集训：动态规划4 ——树状dp 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。动态规划基础4 (dynamicprogramming)
——树型动规
由于本蒟蒻水平实在是有限,若有遗漏和错误欢迎大家立即指出并请多多包涵!
——bydsy
什么是树?
父亲
儿子
根
例1:没有上司的舞会
题目大意:
n个人形成一个关系树,每个节点代表一个人,节点的根表示这个人的唯一的直接上司,只有根没有上司。要求选取一部分人出来,使得每2个人之间不能有直接的上下级的关系,求最多能选多少个人出来,并且求出获得最大人数的选人方案是否唯一。
简单的染色统计是不正确的
例1:没有上司的舞会
这是一个经典的树型动态规划。
第一步:确定状态
用f[i][0]表示不选择i点时,i点及其子树能选出的最多人数,f[i][1]表示选择i点时,i点及其子树的最多人数。
第二步:确定状态转移方程
f[i][0]=Σ(max(f[j][0],f[j][1]))
f[i][1]=1+Σf[j][0]
(j是i的儿子!!)
边界:f[i][0]=0,f[i][1]=1--------i是叶子节点
结果为max(f[root][0],f[root][1])
例1:没有上司的舞会
第三步:确定编程实现方式
显然只有记忆化搜索了!(实际上就是一个树的后序遍历~~~~)
voiddfs(longx)
{
v[x]=1;
for(longi=1;i<=n;i++)
{
if((!v[i])&&(fa[i]==x))
{
dfs(i);
f[x][0]+=max(f[i][1],f[i][0]);
f[x][1]+=f[i][0];
}
}
}
例1:没有上司的舞会
例2:二叉苹果树
有一棵苹果树,苹果树的是一棵二叉树,共N个节点,树节点编号为1~N,编号为1的节点为树根,边可理解为树的分枝,每个分支都长着若干个苹果,现在要要求减去若干个分支,保留M个分支,要求这M个分支的苹果数量最多。
例2:二叉苹果树
第一步:确定状态
f[u][j]表示在以u为根的子树保留j个分支可以得到的最大苹果数量
第二步:确定状态转移方程
F[u][j]=max(f[u][k]+f[v][j–k-1]+W)
v分别是u的儿子,w为u到v边上的苹果数目,k属于[0,j]
voiddfs(intu)
{
vis[u]=1;
inti,v,w,j,k,son=0;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;w=e[i].w;
if(vis[v]==1)continue;
dfs(v);
for(k=m;k>=1;k--)
{
for(j=1;j<=k;j++)//在v节点的子树中选择j条边
if(f[u][k]<f[u][k-j]+f[v][j-1]+w)
f[u][k]=f[u][k-j]+f[v][j-1]+w;
//u与v有一条边,所以加上dp[v][j-1]
}
}
}
例3:Strategicgame
一城堡的所有的道路形成一个n个节点的树,如果在一个节点上放上一个士兵,那么和这个节点相连的边就会被看守住,问把所有边看守住最少需要放多少士兵。
树的最小点覆盖!