首页 > 代码库 > 【DP合集】tree-knapsack

【DP合集】tree-knapsack

2024-10-29 06:58:02   211人阅读

Description

给出一个 N 个节点的有根树，点编号 1 ～ N ，编号为 i 的点有权值 v i 。请选出一个包含树根的，点数 不超过 K 的连通块，使得点权和最大。

Input

输入的第一行有二个整数 N , K ( K ≤ N ≤ 3000) 。 
接下来一行 N 个整数，第 i 个数描述编号为 i 的点的父亲编号，若该数为 0 ，则表示点 i 为树根。 
接下来一行 N 个整数，第 i 个数描述编号为 i 的点的权值。

Output

输出一行一个整数，描述最大的点权和。保证答案不会超过 231?1231?1。

 

题解：
这个题目我还是建议先自行百度树形背包，不然听不懂我在说什么！(不过估计看懂后就不会听我讲了QAQ)，好了，这是道树形背包的裸题，状态是显然的，dp[i][j]表示dp到i号节点可以放j个节点的最大点权和，保障连通也很简单，只要让他强制选当前i号节点就可以，接下了的问题就是转移了，显然我们可以把每棵子树单词一个不定代价和价值的背包，那么我们先把当前节点也当成一个同样的背包，然后每次将一个子树与当前的根节点的不定背包合并，然后枚举下一棵子树，没听懂没关系，代码很清楚。
 
代码： 
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<cstring>
const int MAXN=3010;
using namespace std;
struct edge{
    int first;
    int next;
    int to;
}a[MAXN*5];
int n,m,num=0,roof;
int dp[MAXN][MAXN];
int W[MAXN];
 
void cl(){
    memset(dp,0,sizeof(dp));
}
 
void addedge(int from,int to){
    a[++num].to=to;
    a[num].next=a[from].first;
    a[from].first=num;
}
 
void dfs(int now,int fa,int w){
    if(w==0) return;
    for(int i=a[now].first;i;i=a[i].next){
        int to=a[i].to;
        if(to==fa) continue;
        for(int j=1;j<=w;j++) dp[to][j]=dp[now][j];
        dfs(to,now,w-1);
        for(int j=1;j<=w;j++) dp[now][j]=max(dp[now][j],dp[to][j-1]+W[to]);
    }
}
 
int main(){
    cl();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        if(x==0) roof=i;
        else addedge(i,x),addedge(x,i);
    }
    for(int i=1;i<=n;i++) scanf("%d",&W[i]);
    dfs(roof,0,m);
    printf("%d",dp[roof][m-1]+W[roof]);
}

 

 

【DP合集】tree-knapsack


联系
我们