洛谷 P2015 二叉苹果树 (树上背包)

时间：2022-04-15 15:29:19

洛谷 P2015 二叉苹果树 (树上背包)

一道树形DP，本来因为是二叉，其实不需要用树上背包来干（其实即使是多叉也可以多叉转二叉），但是最近都刷树上背包的题，所以用了树上背包。

首先，定义状态\(dp[x][i]\)表示在节点\(x\)保留\(i\)个边所获得的最大苹果数，定义状态时一定要选对状态并且定义清晰（状态中包括了当前节点吗？目标状态是怎样的？）。一开始我就是因为状态定义错误，所以卡了半天，之后重新定义状态后几分钟就切了这道题。

然后是普通的树上背包状态转移

\[dp[x][i]=max(dp[x][i], dp[x][i-k]+dp[son_x][k-1]+val)
\]

注意，此次已优化了一维，所以\(i\)要降序遍历。

AC Code:

#include <cstdio>

#include <vector>

#define MAXN 110

#define MAX(A,B) ((A)>(B)?(A):(B))

#define MIN(A,B) ((A)<(B)?(A):(B))

using namespace std;

int n,q,dp[MAXN][MAXN];

struct nod{

    int v, val;

    nod(int v, int val):v(v),val(val){}

};

vector <nod> mp[MAXN];

int dfs(int x, int fa){

    int cnt=1,sz=0;

    for(register int i=0;i<mp[x].size();++i){

        int v=mp[x][i].v,val=mp[x][i].val;

        if(fa==v) continue;

        sz=dfs(v, x);

        cnt+=sz;

        for(register int j=q;j>=0;--j)

            for(register int k=1;k<=MIN(sz, j);++k)

                dp[x][j]=MAX(dp[x][j], dp[v][k-1]+dp[x][j-k]+val);

    }

    return cnt;

}

int main()

{

    scanf("%d %d", &n, &q);n--;

    while(n--){

        int a,b,val;

        scanf("%d %d %d", &a, &b, &val);

        mp[a].push_back(nod(b, val));

        mp[b].push_back(nod(a, val));

    }

    dfs(1,0);

    printf("%d", dp[1][q]);

    return 0;

}

/*

dp[x][i]=MAX(dp[x][i], dp[x][i-k]+dp[son_x][k-1]+val)

*/

相关文章