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

【DP合集】tree-knapsack

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