首页 > 代码库 > zoj3201（树形dp）
zoj3201（树形dp）
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3201
题意：给一棵树, n结点<=1000, 和K <=200, 找这棵树上找大小为k的子树, 使其点权值最大。
分析：dp[u][j]表示以点u为根节点的子树含有j个节点的最大值，dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]).
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 110#define clr(a) (memset(a,0,sizeof(a)))using namespace std;struct edge{ int next,v; edge(){} edge(int v,int next):v(v),next(next){}}e[N*2];int head[N],tot,n,m;int dp[N][N],val[N];void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int u,int fa){ for(int i=1;i<=m;i++)dp[u][i]=val[u]; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dfs(v,u); for(int j=m;j>=1;j--) for(int k=0;k<j;k++)//肯定得含有节点u，所以k<j. dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]); }}int main(){ int u,v; while(scanf("%d%d",&n,&m)>0) { tot=0; memset(head,-1,sizeof(head));clr(dp); for(int i=0;i<n;i++)scanf("%d",&val[i]); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(0,-1); int ans=0; for(int i=0;i<n;i++)ans=max(ans,dp[i][m]); printf("%d\n",ans); }}
zoj3201（树形dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。