啊！DP!

顾名思义，树形DP就是在树上所做的动态规划。我们一般所做的动态规划多是线性的，线性DP我们可以从前向后或从后向前两种方法，不妨类比一下，在树上我们同样可以有两种方法，从根向树叶或者从树叶向根。从根向树叶传值的题不多见，而从叶向根传送值的题较多，下面我们主要来分析这种题。

luogu1352没有上司的舞会

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

分析：

把该题抽象到一颗树中，设i的下属就是他的儿子，则有两种情况：

如果i参加，他的儿子就不能参加。

如果i不参加，他的儿子可参加可不参加。

所以设f[i][1]表示i参加，f[i][0]表示i不参加，则有

f[i][0]+=max(f[j][0],f[j][1]);
f[i][1]+=f[j][0]+w[i];       //j是i的儿子

所以

ans=max(f[i][1],f[i][0])   //最大快乐指数

得到基础代码：（很粗略，不过好懂）

#include<cstdio> 
#include<iostream>
using namespace std;
const int maxn=6005;
int f[maxn][2],n,r[maxn];
int son[maxn][maxn],tot[maxn];
int vis[maxn];
int end;
void tree_dp(int x)
{
    for (int i=1;i<=tot[x];i++)
    {
        int y=son[x][i];   //哪个儿子 
        tree_dp(y);    //刷新y的快乐指数 
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=f[y][0];
    }
}
void work()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    scanf("%d",&f[i][1]);  //父亲（上司）要去的情况，要加本身的快乐指数 
    int k,l;
    for (int i=1;i<=n;i++)
    {
       scanf("%d%d",&l,&k);
       if(l!=0&&k!=0)    
       {
              son[k][++tot[k]]=l; 
               vis[l]=1;    //l是儿子 
       }
    }
    for (int i=1;i<=n;i++)
    {
        if(!vis[i]) //找根节点（非儿子） 
        {
        end=i;
        break;    
        }
    }
    tree_dp(end);
    printf("%d",max(f[end][0],f[end][1]));
}
int main()
{
    work();
    return 0;
}

在这里就要说一下vector了，真的很好用

 STL之vector

关于DP有一点很重要——多叉树转二叉树。

树有很多种，二叉树是一种人人喜欢的数据结构，简单而且规则。
但一般来说,树形动规的题目很少出现二叉树,因此将多叉树转成二叉树就是一种必备的手段，方法非常简单,“左儿子,右兄弟” 。
就是将一个节点的第一个儿子放在左儿子的位置，下一个儿子，即左儿子的第一个兄弟,放在左儿子的右儿子位置上，再下一个兄弟接着放在右儿子的右儿子，以此类推。

代码：

scanf("%d%d",&u,&v)  //v的父亲是u
if(last[u]==0)l[u]=v;    //将v作为u的左儿子
else {
r[last[u]]=v;  //将v作为u的最后一个子孙的右儿子
last[u]=v;  //last数组记录u的最后一个子孙
}  

为什么要这样转二叉，等会你就知道了。(好神秘)

洛谷 2014 选课

分析：以样例为例，课程之间关系如下图：

  转换为

 

在转化后的二叉树上，我们如果选第1，就必须先选2，如果选3，不一定要选2。

设dp[i][j]表示选到第i门课，还要选j门课的最大学分，那么分两种情况讨论：

如果选i，则还要在l[i]上选k门，并且在r[i]上选就j-k-1门。

如果不选i，则只能在r[i]上选j门，0<=k<j。

现在你知道这种转二叉树的好处了吧。

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄