题解 P2015 【二叉苹果树】

stone_juice石汁 · 2019-10-11 09:43:44 · 题解

前言

本蒟蒻初次接触树形dp，不是很懂DALAO们把树枝上苹果转化为结点上苹果的做法，状态转移方程沃也不知道DALAO们怎么把3个方程合在一起的。我只好发一篇题解，介绍一下我的蒟蒻做法，顺便帮助一下有同样困惑的童鞋qaq。

思路

这道题正解是树形dp，还算一道比较基础的树形dp吧。

观察题目条件，我们得知，至少需要保留q条树枝。

那么，树枝的保留条数是要一定要加入状态转移方程的。加上我们要在扫整棵树时必须得知的结点信息，所以我们自然可以定义这么一个二维dp数组。

定义dp[maxn][maxm]数组，dp[i][j]表示为，当前结点为i，保留树枝条数为j的情况下，所留下苹果数的最大值。

既然这是一个树形结构，那么我们自然还要维护下面这么几个值：

这四个值均可以在递归建树的时候求得。我们现在要用这四个值写状态转移方程。

首先来看几个特殊情况：

2$、当 $j == 0$ ，说明保留树枝条数为$0$，也就是不保留树枝。树枝都不保留，苹果自然也没有，所以也是返回$0

然后就是状态转移方程了。

我们枚举一个中间量 k 。这个 k 代表为我们给左儿子分配的树枝数。这是什么意思呢？其实就是给左边的子树的树枝不能超过 k条的意思。也就是令左子树的树枝数最多为k。

我们令左子树的树枝数最多为k，右子树的树枝数显然最多为j-k。 显然我们可以得到一个粗略的转移方程：

dp[i][j] = max(dp[ls(i)][k-1] + dp[rs(i)][j - k-1] + la[i] + ra[i])

这里有些人注意到了，转移方程里写分配数分别是k-1和j-k-1，而非k和j-k。这是因为往左右儿子方向走，你还要再走过一条树枝才能到达儿子结点，所以实际上分配数是比原来少1的

但是且慢，我们看似这个转移方程是对的，但是这里却分了2种特殊的情况。

所以，最后最终的转移方程实际上是这个样子的：

dp[rs[i]][j-1] + ra[i] ~~~ (k=0)
dp[ls[i]][j-1] + la[i] ~~~ (k=j)
dp[ls[i]][k-1] + dp[rs[i]][j - k-1] + la[i] + ra[i] ~~~ (k \ne0,k\ne j)

当然这个转移方程不是直接写上去的。由于要不断选取左子树和右子树，所以上述过程实际上是递归完成的。

这就是最主要的部分了。

Code

主要的转移方程我觉得应该是讲清楚了。关于建树的问题，代码注释里有详细的解答。

所以直接看代码吧qaq

#include <bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define inf 0x3f3f3f3f
#define maxn 1005
#define maxm 105

using namespace std;

int n, q, ls[maxm], rs[maxm], la[maxm], ra[maxm];
//n,q如题，ls[x],rs[x]代表x的左右儿子，la[x],ra[x]代表连向左右儿子的边上的苹果 
int dp[maxn][maxm]; 
int head[maxn], nxt[maxn], to[maxn], val[maxn], cnt;//这是一堆建边要用的东西qaq 

void add_edge(int u, int v, int w)//邻接链表建边..貌似没什么好说的 
{
    nxt[++ cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    val[cnt] = w;
}

void build(int x, int fa)//x,fa分别是当前节点和父亲节点,此函数为建树 
{
    int g = 0;//g是计数器，用来分配左儿子和右儿子，下面有解释
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = to[i];
        if(y != fa)//如果不为父节点，就一定为儿子节点 
        {
            g ++;
            if(g == 1) ls[x] = y, la[x] = val[i];//g==1分配到左儿子。顺便处理边权 
            else rs[x] = y, ra[x] = val[i];//g==2说明左儿子分配过了，分配到右儿子 
            build(y, x);//向下递归建树 
        }
    }
}

int _find(int i, int j) //dp[i][j]以i为根，保留j个树枝的最大值
{
    if(ls[i] == 0 && rs[i] == 0) return 0;//无左右儿子说明为叶子，叶子没有儿子树枝。 
    if(j == 0) return 0;//一个树枝都不分配，也就没有苹果了。 
    if(dp[i][j] > 0) return dp[i][j];//一个优化剪枝：这个点已经被更新过了就直接返回。 
    for(int k = 0; k <= j; k ++)//枚举给左儿子分配的树枝数k，给右儿子分配的即为 j-k。 
    {
        if(k == 0) dp[i][j] = max(dp[i][j], _find(rs[i], j - 1) + ra[i]);//k==0，相当于全给右儿子分配 
        else if(k == j) dp[i][j] = max(dp[i][j], _find(ls[i], j - 1) + la[i]);//k==j，相当于全给左儿子分配 
        dp[i][j] = max(dp[i][j], _find(ls[i], k - 1) + _find(rs[i], j - k - 1) + la[i] + ra[i]);
        //这种情况两边均有分配。
        //由于走到儿子结点都需要经过一条树枝，所以实际上分配数都要-1。 
    }
    return dp[i][j];
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n - 1; i ++)
    {
        int ui, vi, wi;
        scanf("%d%d%d", &ui, &vi, &wi);
        add_edge(ui, vi, wi);
        add_edge(vi, ui, wi);//建无向边 
    }
    build(1, 0);//建树 
    printf("%d", _find(1, q));//输出 
    return 0;
}

~~码字不易，悄悄要个赞没关系吧~~

题解 P2015 【二叉苹果树】

前言

思路

Code