luoguP2015（简单树形DP）

题目链接：https://www.luogu.org/problemnew/show/P2015

题意：给定一颗结点个数为n的树，有n-1条边，每条边有个权值，树根为1。现在给出q <=n，问剪枝后保留q条边后的边的权值最大是多少。

思路：首先要知道这道题有个隐含条件，如果某条边被保留，那么从根节点到这个点路径上的所有点都必须保留。

　　　我们用dp[i][j]表示顶点i的子树上保留j条边的最大权值和是多少。

　　　给出状态转移方程：dp[x][j]=max(dp[x][j] , dp[x][j-1-k]+dp[y][k]+edge[i].w)

　　　其中x是当前结点，y是x的一个子结点，k表示结点y上保留的边数，0<j<=min(siz[x],q)，0=<k<=min(siz[y],j-1)。因为要把x和y之间的边算上，所以是j-1-k。

　　　其中j需要倒序枚举，类似01背包。

AC代码：

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

struct node{

    int v,w,nex;

}edge[maxn<<];

int n,q,cnt,head[maxn],siz[maxn];

int dp[maxn][maxn];

void adde(int u,int v,int w){

    edge[++cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt;

}

void dfs(int x,int f){

    for(int i=head[x];i;i=edge[i].nex){

        int y=edge[i].v;

        if(y==f) continue;

        dfs(y,x);

        siz[x]+=siz[y]+;

        for(int j=min(siz[x],q);j;--j)

            for(int k=;k<=min(siz[y],j-);++k)

                dp[x][j]=max(dp[x][j],dp[x][j--k]+dp[y][k]+edge[i].w);

    }

}

int main(){

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

    for(int i=;i<n;++i){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        adde(u,v,w);

        adde(v,u,w);

    }

    dfs(,-);

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

    return ;

}

巴特西

luoguP2015（简单树形DP）

最新文章

热门文章