首页 > 代码库 > Ural 1018 (树形DP+背包+优化)
Ural 1018 (树形DP+背包+优化)
题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17662
题目大意:树枝上间连接着一坨坨苹果(不要在意‘坨‘),给定留下m根树枝,问最后剩下的最多苹果是多少。
解题思路:
其实意思和Vijos 1180(选课)的意思差不多。只不过权在边而已。
首先建无向图dfs。
for(f+1...j....cost)
for(1....k...j-cost)
其中f为当前已经dfs子结点个数。之所以+1,是因为当前点也需要分配一根树枝才能取到这个点的苹果。
f+=dfs(t),dfs(t)返回的是子点t的f+1。
其实可以直接把f+1写成m+1, 不过要多好多次没必要的循环。
最后结果就是dp[1][m+1],注意由于树结构,1上的苹果是默认都能取到,但是按照这种DP方式要取到1上苹果,还需要加一个虚枝才行,也就是为什么是m+1。
#include "cstdio"#include "queue"#include "iostream"#include "cstring"using namespace std;#define maxn 105int n,m,dp[maxn][maxn],head[maxn],tol;struct Edge{ int next,to,w;}e[maxn*2];void addedge(int u,int v,int w){ e[tol].to=v; e[tol].next=head[u]; e[tol].w=w; head[u]=tol++;}int dfs(int root,int pre){ int cost=1,i=root,f=0; for(int a=head[root];a!=-1;a=e[a].next) { int t=e[a].to; if(t==pre) continue; f+=dfs(t,root); for(int j=f+1;j>=1;j--) for(int k=1;k<=j-cost;k++) dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]+e[a].w); } return f+cost;}int main(){ //freopen("in.txt","r",stdin); int u,v,w; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs(1,1); printf("%d\n",dp[1][m+1]);}
2867777 | neopenx | URAL | 1018 | Accepted | 418 | 31 | G++ 4.9 | 917 | 2014-10-20 16:15:45 |
Ural 1018 (树形DP+背包+优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。