首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。