首页 > 代码库 > hiho1055 - 树形dp转换成背包
hiho1055 - 树形dp转换成背包
题目链接
输入:一棵树,每个节点一个权值。
输出:包括1号节点在内的m个节点组成的连通分量的权值和的最大值
/**********************************************/
计 dp(i,j) 为以i为根的子树选中j个点(包括i)时的最大权值和。则dp(1,m)即为所求。
方程:
{
dp[i][0] = 0;
dp[i][1] = value[i];
foreach child c of i
for j = m...2
for k = 1...j-1
dp[i][j] = max(dp[i][j],dp[i][j-k]+dp[c][k])
}
因为dp的核心就是记忆化搜索,所以自下向上遍历整棵树,处理完一个节点就标记一下,下次用到这个节点的时候就不用再递归了。
这里我用getCnt()函数计算了一下以每个节点i为根的子树中节点的数目cnt(i),为的是缩小求dp(i,j)中j和k的上限,由m变为MIN(m,cnt(i)),应该不会提速多少
#include <set> #include <map> #include <stack> #include <queue> #include <cmath> #include <vector> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b)) #define MIN(a,b) ((a)<=(b)?(a):(b)) #define long long LL #define OO 0x0fffffff using namespace std; const int N = 111; struct Edge{ int to; int next; }; int eid = 0; Edge edges[N*2]; int heads[N]; void addEdge(int a,int b){ edges[eid].to = a; edges[eid].next = heads[b]; heads[b] = eid++; edges[eid].to = b; edges[eid].next = heads[a]; heads[a] = eid++; } int m,n; int dp[N][N],cnt[N],visited[N]; void getCnt(int id){ visited[id] = 1; for(int cur = heads[id];cur!=-1;cur=edges[cur].next){ int cid = edges[cur].to; if(!visited[cid]) { if(!cnt[cid]) getCnt(cid); cnt[id] += cnt[cid]; } } cnt[id] += 1; } void traverse(int id){ visited[id] = 1; for(int cur=heads[id];cur!=-1;cur=edges[cur].next){ int cid = edges[cur].to; if(!visited[cid]){ if(visited[cid]!=2) traverse(cid); for(int i=MIN(m,cnt[id]);i>=2;i--){ for(int j=1;j<MIN(i,cnt[cid]+1);j++){ dp[id][i]=MAX(dp[id][i],(dp[id][i-j]+dp[cid][j])); } } } } visited[id] = 2; } int main(){ scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",dp[i]+1); int a,b; memset(heads,-1,sizeof(heads)); for(int i=0;i<n-1;i++){ scanf("%d%d",&a,&b); addEdge(a,b); } memset(cnt,0,sizeof(cnt)); memset(visited,0,sizeof(visited)); getCnt(1); memset(visited,0,sizeof(visited)); traverse(1); printf("%d\n",dp[1][m]); return 0; }
hiho1055 - 树形dp转换成背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。