树形动态规划

作者: Mr_chong | 来源:发表于2016-12-07 20:17 被阅读299次

    树形动态规划,顾名思义就是树+DP,先分别回顾一下基本内容吧:
    动态规划:
    问题可以分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题,称为多阶段决策问题。动态规划就是解决多阶段决策最优化问题的一种思想方法。
    阶段:
    将所给问题的过程,按时间或空间(树归中是空间,即层数)特征分解成若干相互联系的阶段,以便按次序去求每阶段的解。
    状态:
    各阶段开始时的客观条件叫做状态。
    决策:
    当各段的状态取定以后,就可以做出不同的决定,从而确定下一阶段的状态,这种决定称为决策。 (即孩子节点和父亲节点的关系)
    策略:
    由开始到终点的全过程中,由每段决策组成的决策序列称为全过程策略,简称策略。
    状态转移方程:
    前一阶段的终点就是后一阶段的起点,前一阶段的决策选择导出了后一阶段的状态,这种关系描述了由k阶段到k+1阶段(在树中是孩子节点和父亲节点)状态的演变规律,称为状态转移方程。
    目标函数与最优化概念:
    目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径,经过按题目具体性质所确定的运算以后,使全过程的总效益达到最优。
    树的特点与性质:
    1、 有n个点,n-1条边的无向图,任意两顶点间可达
    2、 无向图中任意两个点间有且只有一条路
    3、 一个点至多有一个前趋,但可以有多个后继
    4、 无向图中没有环;
    拿到一道树规题,我们有以下3个步骤需要执行:

    1. 判断是否是一道树规题:即判断数据结构是否是一棵树,然后是否符合动态规划的要求。如果是,那么执行以下步骤,如果不是,那么换台。
    2. 建树:通过数据量和题目要求,选择合适的树的存储方式。如果节点数小于5000,那么我们可以用邻接矩阵存储,如果更大可以用邻接表来存储(注意边要开到2*n,因为是双向的。这是血与泪的教训)。如果是二叉树或者是需要多叉转二叉,那么我们可以用两个一维数组brother[],child[]来存储(这一点下面会仔细数的)。
    3. 写出树规方程:通过观察孩子和父亲之间的关系建立方程。我们通常认为,树规的写法有两种:
      a.根到叶子: 不过这种动态规划在实际的问题中运用的不多。
      b.叶子到根: 既根的子节点传递有用的信息给根,完后根得出最优解的过程。这类的习题比较的多。
      注意:这两种写法一般情况下是不能相互转化的。但是有时可以同时使用具体往后看。
      以下即将分析的题目的目录及题目特点:
      1、加分二叉树:区间动规+树的遍历;
      2、二叉苹果树:二叉树上的动规;
      3、最大利润:多叉树上的动规;
      4、选课:多叉树转二叉;
      5、选课(输出方案):多叉转二叉+记录路径;
      6、软件安装:判断环+缩点+多叉转二叉;
      【4、5、6属于依赖问题的变形】
      1、加分二叉树
      描述 Description
        设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数
        若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
        试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;
        (1)tree的最高加分
        (2)tree的前序遍历
      输入格式 Input Format
      第1行:一个整数n(n<30),为节点个数。
      第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。
      输出格式 Output Format
        第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。
        第2行:n个用空格隔开的整数,为该树的前序遍历。
      样例输入 Sample Input
      5
      5 7 1 2 10
      样例输出 Sample Output
      145
      3 1 2 4 5
      分析:
      这道题我们可以发现可以让左子树最大,右子树最大,从而达到整棵树的权值最大,符合最优化原理,所以它是一道简单的动态规划,而不是树规,样例给的是中序遍历,就是用f[i][j]表示从i到j的最大值,方程很简单,第一问可以轻松解决。我们看第二问,要求的是前序遍历,r[i][j]表示从i到j的根,递归求解。
      代码如下:

    include<iostream>

    include<cmath>

    include<cstdio>

    include<cstring>

    include<algorithm>

    define INF -999999999

    using namespace std;
    int N,a[40],f[40][40],r[40][40];
    void init()
    {
    scanf("%d",&N);
    for(int i=0;i<=N;i++)
    for(int j=0;j<=N;j++)
    f[i][j]=1;
    for(int i=1;i<=N;i++)
    {
    scanf("%d",&a[i]);
    f[i][i]=a[i];
    r[i][i]=i;
    }
    }
    void DP()
    {
    for(int l=1;l<=N;l++)
    for(int i=1;i<=N;i++)
    {
    int j=i+l;
    if(j>N) continue;
    int temp=INF;
    for(int k=i;k<=j;k++)
    if(temp<(f[i][k-1]f[k+1][j]+a[k]))
    {
    temp=f[i][k-1]
    f[k+1][j]+a[k];
    r[i][j]=k;
    }
    f[i][j]=temp;
    }
    printf("%d\n",f[1][N]);
    }
    void work(int x,int y)
    {
    if(r[x][y]!=0) cout<<r[x][y]<<' ';
    if(r[x][r[x][y]-1]!=0) work(x,r[x][y]-1);
    if(r[r[x][y]+1][y]!=0) work(r[x][y]+1,y);
    }
    int main()
    {
    init();
    DP();
    work(1,N);
    return 0;
    }

    小结:看见一道题,应该看清算法,不是有个二叉树就是树规。

    2、二叉苹果树
    描述 Description
    有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点)。这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。
    我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树:
    2 5
    \ /
    3 4
    \ /
    1
    现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。
    给定需要保留的树枝数量,求出最多能留住多少苹果。
    输入格式 Input Format
    第1行2个数,N和Q(1<=Q<= N,1<N<=100)。
    N表示树的结点数,Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。每行3个整数,前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。
    输出格式 Output Format
    一个数,最多能留住的苹果的数量。
    样例输入 Sample Input
    5 2
    1 3 1
    1 4 10
    2 3 20
    3 5 20
    样例输出 Sample Output
    21
    时间限制 Time Limitation
    1s
    分析:
    明确这是树规,的的确确的树规,如假包换的树规。
    我们一般用邻接矩阵或邻接表存树,本题可以用邻接矩阵。
    我们发现,做普通DP时,每个权值都是在点上的,从没有在点与点之间过,强迫症,我们把没个边的权值存在子节点上。
    第一步要做的是建树,本题我们要用已有的邻接矩阵建立一颗二叉树,tree[i][1]表示i的左子树,tree[i][2]表示i的右子树,然后递归建树。
    然后我们再进行树规,树规一般都是用记忆化搜索来写的,f[i][k]表示以i为根的子树保留k个枝的最大值,方程:f[v][k]=max(f[v][k],(f[tree[v][1]][i]+f[tree[v][2]][k-i-1]+num[v])),f[1][Q+1]就是最后答案。
    代码如下:

    include<iostream>

    include<cmath>

    include<cstring>

    include<cstdio>

    include<algorithm>

    using namespace std;
    int N,Q,a[110][110],num[110],tree[110][5],f[110][110];
    void init()
    {
    scanf("%d%d",&N,&Q);
    for(int i=0;i<=N;i++)
    for(int j=0;j<=N;j++)
    a[i][j]=a[i][j]=-1;
    for(int i=1;i<N;i++)
    {
    <span style="white-space:pre"> </span> int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    a[x][y]=a[y][x]=z;
    }
    }
    void maketree(int v);
    void build(int x,int y,int lr)
    {
    num[y]=a[x][y];
    tree[x][lr]=y;
    a[x][y]=-1;a[y][x]=-1;//记忆化,避免重复建树。
    maketree(y);//递归完成根到叶的建树。
    }
    void maketree(int v)
    {
    int lr=0;
    for(int i=0;i<=N;i++)
    <span style="white-space:pre"> </span> if(a[v][i]>=0)
    {
    lr++;//分别记到左子树或右子树上。
    build(v,i,lr);
    if(lr==2) return;
    }
    }
    void dfsDP(int v,int k)
    {
    if(k==0) f[v][k]=0;
    else if(tree[v][1]==0&&tree[v][2]==0) f[v][k]=num[v];
    else
    {
    f[v][k]=0;
    for(int i=0;i<k;i++)
    {
    if(f[tree[v][1]][i]==0) dfsDP(tree[v][1],i);
    if(f[tree[v][2]][k-i-1]==0) dfsDP(tree[v][2],k-i-1);
    f[v][k]=max(f[v][k],(f[tree[v][1]][i]+f[tree[v][2]][k-i-1]+num[v]));
    }
    }
    }
    int main()
    {
    init();
    maketree(1);//建树。
    dfsDP(1,Q+1);
    printf("%d\n",f[1][Q+1]);
    return 0;
    }

    小结:树规我们一般都用二叉树,二叉树可以用静态数组存储。下面给出几道多叉的题目,看看怎么解决。

    3、最大利润
    描述 Description
    政府邀请了你在火车站开饭店,但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径,每个火车站最多有50个和它相连接的火车站。
    告诉你每个火车站的利润,问你可以获得的最大利润为多少。
    例如下图是火车站网络:

    最佳投资方案是在1,2,5,6这4个火车站开饭店可以获得利润为90
    输入格式 Input Format
    第一行输入整数N(<=100000),表示有N个火车站,分别用1,2。。。,N来编号。接下来N行,每行一个整数表示每个站点的利润,接下来N-1行描述火车站网络,每行两个整数,表示相连接的两个站点。
    输出格式 Output Format
    输出一个整数表示可以获得的最大利润。
    样例输入 Sample Input
    6
    10
    20
    25
    40
    30
    30
    4 5
    1 3
    3 4
    2 3
    6 4
    样例输出 Sample Output
    90
    时间限制 Time Limitation
    1s
    分析:
    这是一棵多叉树,每个节点只和它的孙子节点有关,所以这道题是动规,的的确确的树规。
    按照上一题的思路,我们先建树,N比较大,只能用邻接表来存了,我们取1为根。
    最后一步,我们知道有两个方向:一个是i要,则i的儿子不要;一个是i不要,则i的儿子可要可不要,我们用f[i][0]和f[i][1]分别表示,最后输出max(f[1][0],f[1][1])。题目完成!
    代码如下:

    include<iostream>

    include<cmath>

    include<cstring>

    include<cstdio>

    include<algorithm>

    using namespace std;
    int N,a[100010],f[100010][2]={},len=0;
    int linkk[100010]={};
    struct edge
    {
    int next,y;
    }e[200010];
    void insert(int xx,int yy)//邻接表储存树。
    {
    e[++len].y=yy;
    e[len].next=linkk[xx];
    linkk[xx]=len;
    }
    void init()
    {
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=1;i<N;i++)
    {
    int xx,yy;
    scanf("%d%d",&xx,&yy);
    insert(xx,yy);
    insert(yy,xx);
    }
    }
    void dfsDP(int r,int fa)
    {
    for(int i=linkk[r];i;i=e[i].next)
    if(e[i].y!=fa)//因为存的是双向边,所以需要避免找会父亲节点。
    {
    dfsDP(e[i].y,r);
    f[r][0]+=f[e[i].y][1];//当前点要那么当前的孩子就不要。
    f[r][1]+=max(f[e[i].y][0],f[e[i].y][1]);//当前的不要那么当前点的孩子可要可不要。
    }
    f[r][0]+=a[r];//加上当前点的利润。
    }
    int main()
    {
    init();
    dfsDP(1,1);
    printf("%d\n",max(f[1][0],f[1][1]));//本题中我们以1为根。
    return 0;
    }
    小结:这道多叉树的题目是比较简单的,只要建树然后找孩子与父亲的关系之后状态转移即可,下面看一道繁琐点的。

    4、选课
    描述 Description
    学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N(N<300)门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。

    在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号,依次为1,2,3,…。 例如:

    上例中1是2的先修课,即如果要选修2,则1必定已被选过。同样,如果要选修3,那么1和2都一定已被选修过。
      你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
    输入格式 Input Format
    输入文件的第一行包括两个整数N、M(中间用一个空格隔开),其中1≤N≤300,1≤M≤N。
    以下N行每行代表一门课。课号依次为1,2,…,N。每行有两个数(用一个空格隔开),第一个数为这门课先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。学分是不超过10的正整数。
    输出格式 Output Format
    只有一个数:实际所选课程的学分总数。
    样例输入 Sample Input
    7 4
    2 2
    0 1
    0 4
    2 1
    7 1
    7 6
    2 2
    样例输出 Sample Output
    13
    时间限制 Time Limitation
    1s

    分析:
    还是分析它是什么问题,一个依赖于另一个,结果就呵呵了,我们很快联想到了依赖性背包问题,发现完全不知道怎么写,这里我们谈一谈树规和依赖性背包的不同之处:依赖性背包只能是一个物品依赖另一个物品,而这个被依赖的物品却无法依赖其他物品了,也就是说两个物品只有直接关系或者是没关系,而没有间接关系,而树规就不一样了,父亲和儿子有关。
    确定是树规了,就按部就班,建树,邻接矩阵就行。
    然后树规:f[i][j]表示以i为节点的根的选j门课的最大值,然后有两种情况: i不修,则i的孩子一定不修,所以为0;i修,则i的孩子们可修可不修(在这里其实可以将其转化为将j-1个对i的孩子们进行资源分配的问题,也属于背包问题);答案是f[1][m]。问题完美解决。
    有点麻烦,我们可以把它简化一下,就像第二题中父亲只跟左右儿子有关,左右儿子可以直接存在两个数组里,很方便。这道题是多叉树,我们想把它变为二叉树,就需要我们做一件很重要但又很反人类反社会的事情——多叉转二叉!如下:bi和ci表示i的兄弟和儿子,采用左儿子右兄弟的方法,让兄弟变成儿子(有点邪恶…),不过这个儿子要标记为兄弟,这样建树的话,一颗多叉树就可以变为二叉树了。
    接下来我们再来DP:f[i][j]表示以i为根选j门课的最优解,还是两种情况:1.不选修i,则儿子以下都无法选修了,f[i][j]=f[b[i]][j];2.i选修,则f[i][j]=f[c[i]][k]+f[b[i]][j-k-1]+a[i]。最后两者取最优即可解决。
    代码如下:

    include<iostream>

    include<cmath>

    include<cstdio>

    include<cstring>

    include<algorithm>

    using namespace std;
    int N,M,a[310],c[310],b[310],f[310][310];
    void init()
    {
    scanf("%d%d",&N,&M);
    memset(f,-1,sizeof(f));
    for(int i=1;i<=N;i++)
    {
    int t1,t2;
    scanf("%d%d",&t1,&t2);
    a[i]=t2;
    if(t1==0) t1=N+1;//以N+1为根。
    b[i]=c[t1];
    c[t1]=i;//采用二叉树的储存方式。
    }
    }
    void dfsDP(int x,int y)
    {
    if(f[x][y]>=0) return;
    if(x==0||y==0)
    {
    f[x][y]=0;
    return;
    }
    dfsDP(b[x],y);
    for(int k=0;k<y;k++)
    {
    dfsDP(b[x],k);//不取根结点。
    dfsDP(c[x],y-k-1);//取根节点。
    f[x][y]=max(f[x][y],max(f[b[x]][y],f[b[x]][k]+f[c[x]][y-k-1]+a[x]));
    }
    }
    int main()
    {
    init();
    dfsDP(c[N+1],M);
    printf("%d\n",f[c[N+1]][M]);
    return 0;
    }
    小结:从这道题和上一道题我们看出,多叉树问题我们有两种写法,第一就是直接做多叉树的树规,第二也可以转化为二叉树再动规。后者的代码比较简单好写一些。

    我们学习线性DP时,经常会遇到输出方案的题目,有名的就是ioi的原题《花店橱窗》,我记得当时是递归通过已经求得的f数组来一个一个配对输出,在树规的输出方案题目中,我们一般也是采用这种方式的,看下一个题目,是上一题的加强版!

    5、选课(输出方案)
    题目如上题。
    输出格式 Output Format
    第一行只有一个数,即实际所选课程的学分总数。
    以下N行每行有一个数,表示学生所选课程的课号。
    n行学生选课的课号按从小到大的顺序输出。
    样例输入 Sample Input
    7 4
    2 2
    0 1
    0 4
    2 1
    7 1
    7 6
    2 2
    样例输出 Sample Output
    13
    2
    3
    6
    7
    分析:
    第一问是和上一题一样的,关键是第二问输出方案。
    DP的输出方案,我们一般都用已经得出的f数组来把路径方案递归求出,我们需要先定义一个bool型的ans数组记录,然后做以下操作:如果f[i][j]=f[b[i]][j],那么节点i必然没有取,让ans[i]=0;否则,节点i一定取到了。然后依照上一问,if(f[x][y]==f[b[x]][k-1]+f[c[x]][y-k]+s[x]),那么我们在i节点后选的一定是以上的方案,在这时让ans[i]=1,继续深搜path()即可。
    说的可能不是那么通。
    代码如下:

    include<iostream>

    include<cmath>

    include<cstdio>

    include<cstring>

    include<algorithm>

    using namespace std;
    int N,M,a[510],c[510],b[510],f[510][510];
    bool ans[510];
    void init()
    {
    scanf("%d%d",&N,&M);
    memset(f,-1,sizeof(f));
    for(int i=1;i<=N;i++)
    {
    int t1,t2;
    scanf("%d%d",&t1,&t2);
    a[i]=t2;
    if(t1==0) t1=N+1;//以N+1为根。
    b[i]=c[t1];
    c[t1]=i;
    }
    }
    void dfsDP(int x,int y)
    {
    if(f[x][y]>=0) return;
    if(x==0||y==0)
    {
    f[x][y]=0;
    return;
    }
    dfsDP(b[x],y);
    for(int k=0;k<y;k++)
    {
    dfsDP(b[x],k);//不取根结点。
    dfsDP(c[x],y-k-1);//取根节点。
    f[x][y]=max(f[x][y],max(f[b[x]][y],f[b[x]][k]+f[c[x]][y-k-1]+a[x]));
    }
    }
    void path(int x,int y)
    {
    if(x==0||y==0) return;
    if(f[x][y]==f[b[x]][y]) path(b[x],y);
    else
    {
    for(int k=1;k<=y;k++)
    if(f[x][y]==f[b[x]][k-1]+f[c[x]][y-k]+a[x])
    {
    path(b[x],k-1);
    path(c[x],y-k);
    ans[x]=1;
    return;
    }
    }
    }
    int main()
    {
    init();
    dfsDP(c[N+1],M);
    printf("%d\n",f[c[N+1]][M]);
    path(c[N+1],M);
    for(int i=1;i<=N;i++)
    if(ans[i]) printf("%d\n",i);
    return 0;
    }
    小结:对于树规输出方案题目,一般都是求解完最优解后原路返回就可以了。

    6、软件安装
    描述 Description
    现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M的计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。
    但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件吗i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么他能够发挥的作用为0。
    我们现在知道了软件之间的依赖关系:软件i依赖Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这是只要这个软件安装了,它就能正常工作。
    输入格式 Input Format
    第1行:N,M (0<=N<=100,0<=M<=500)
    第2行:W1,W2, … Wi, … ,Wn
    第3行:V1,V2, … Vi, … ,Vn
    第4行:D1,D2, … Di, … ,Dn
    输出格式 Output Format
    一个整数,代表最大价值。
    样例输入 Sample Input
    3 10
    5 5 6
    2 3 4
    0 1 1
    样例输出 Sample Output
    5
    时间限制 Time Limitation
    1s
    来源 Source
    haoi2010
    分析:
    这道题看起来和刚刚的《选课》并没有很大的差别,刚开始我甚至以为唯一的区别就是选课每个物品体积为1,而本题物品体积不同而已,但是深入思考,还要很大差别。
    本题没有说这是棵树,所以完全可以是个图,也完全可以有环,例如:a依赖b,b依赖c,而c依赖a。对于这种环,我们一旦要一个,是全都要要的,既然如此,我们不妨把这些环定义为1个点,吧abc这三个点缩成一个新点,然后去完所以环后,就可以发现图已经变为一个多叉树了,为了代码简单,我们再把多叉树转化为二叉树,最后再动规。
    缩点是比较麻烦的,我传承了欧阳学长的好方法,就像钥匙一样可以快速的这道这个点缩点后的新点的下标,具体的代码中有解释,缩点之前的判断是否有环,我们用floyed求有向图的连通性即可。
    多叉转二叉这里不再说,具体看《选课》。
    最后进行动规:
    i的孩子不取f[b[x]][k]=dfs(b[x],k);还是取f[c[x]][y-i]=dfs(c[x],y-i);
    f[b[x]][i]=dfs(b[x],i);
    f[x][k]=max(f[x][k],v[x]+f[c[x]][y-i]+f[b[x]][i]);
    最后答案是f[c[0]][m]。
    代码如下:

    include<iostream>

    include<cmath>

    include<cstdio>

    include<algorithm>

    include<cstring>

    define oo 510

    using namespace std;
    int N,M,w[oo],v[oo],d[oo],b[oo],c[oo],f[oo][5*oo];//注意范围,因为有缩点。
    bool map[oo][oo];
    int t1,t2=0;
    void init()
    {
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) scanf("%d",&w[i]);
    for(int i=1;i<=N;i++) scanf("%d",&v[i]);
    for(int i=1;i<=N;i++)
    {
    int a;
    scanf("%d",&a);
    d[i]=a;
    map[a][i]=1;
    }
    for(int k=1;k<=N;k++)
    for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++)
    if(map[i][k]&&map[k][j])
    map[i][j]=1;
    }
    void merge()//缩点。
    {
    t1=N;
    for(int i=1;i<=t1;i++)
    for(int j=1;j<=t1;j++)
    {
    if(map[i][j]&&map[j][i]&&w[i]>0&&w[j]>0&&i!=j)
    {
    t1++;
    v[t1]=v[i]+v[j];//引进新的点来储存两个互相连通的点。
    w[t1]=w[i]+w[j];
    t2--;//保证t1+t2=N,这是记录合并后点的需要。
    w[i]=w[j]=t2;//这用来记忆该新点下标,方便之后其他点与这个点合并,也是标记该点已经缩过。
    }//这是一个新的环,需要缩点。
    if(map[j][d[j]]&&map[d[j]][j]&&w[d[j]]<0&&w[j]>0)
    {
    w[N-w[d[j]]]+=w[j];
    v[N-w[d[j]]]+=v[j];
    w[j]=w[d[j]];//这几行很强大,是对上一个if的使用,N-w[i]其实就是已经缩过i点的新点下标。
    }//j所依赖的点已经缩过,而且j也在环里。
    if(w[d[j]]<0&&w[j]>0)//j依赖的点已经缩过,但是j不在环里。
    if((map[j][d[j]]&&!map[d[j]][j])||(!map[j][d[j]]&&map[d[j]][j]))
    d[j]=N-w[d[j]];
    }
    }
    int dfsDP(int x,int k)
    {
    if(f[x][k]>0) return f[x][k];
    if(x==0||k<=0) return 0;
    f[b[x]][k]=dfsDP(b[x],k);//不取x点。
    f[x][k]=f[b[x]][k];
    int y=k-w[x];
    for(int i=0;i<=y;i++)
    {
    f[c[x]][y-i]=dfsDP(c[x],y-i);
    f[b[x]][i]=dfsDP(b[x],i);
    f[x][k]=max(f[x][k],f[c[x]][y-i]+f[b[x]][i]+v[x]);
    }
    return f[x][k];
    }
    int main()
    {
    init();
    merge();
    for(int i=1;i<=t1;i++)//多叉转二叉。
    if(w[i]>0)
    {
    b[i]=c[d[i]];
    c[d[i]]=i;
    }
    printf("%d\n",dfsDP(c[0],M));
    return 0;
    }
    小结:这道题很综合,把树规经常考的几个方面出的比较全。

    对于树规,我们就看这6道题目,其中刨去一道区间动规(第一题),剩下的每一道题都可以说把树规的基本操作体现了。
    光看着几道题,我们可以发现,树规题目难其实并不在于状态转移的dfs,我们一直都是花费了很大的劲儿在做预处理之类的东西。这里我需要再提醒一下做树规的步骤,先判断是不是树规,这是最关键的!!!然后建树,对是建树,题目不会把树给你建好,有时候还会只给你个图还带有环的,要谨慎观察,然后再建树或多叉转二叉。最后一步才是树规。

    【总结】树规是动态规划的一种,是在树上做动态规划,比较锻炼我们的代码和动规能力。
    我们一般用递归的形式来做树规,这个树是严格分层的,搞清父亲节点和儿子节点的关系,就可以写了。树的结构其实也决定了比起线性动规,树规的阶段更好划分。

    相关文章

      网友评论

        本文标题:树形动态规划

        本文链接:https://www.haomeiwen.com/subject/zcljmttx.html