首页 > 代码库 > ZOJ 3626(树形DP+背包+边cost)
ZOJ 3626(树形DP+背包+边cost)
题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3626
题目大意：树中取点。每过一条边有一定cost，且最后要回到起点。给定预算m，问最大价值。
解题思路：
首先要注意这题要回到起点，由于树的特殊结构（每个结点只有一个父亲）也就是说，要回到开头，
开销是2倍。所以首先m/=2。
然后就是树形背包的求解，这题的cost在边，所以for写法变成如下：
for(m....j....0)
for(0....k....j-e.cost)
dp[i][j]=max(dp[i][j],dp[i][j-k-e.cost]+dp[t][k]);
for循环的主要变化是0的出现，也就是说某些点的开销可以是0（在父亲上算过了）。
所以初始化也要变成：for(int i=0;i<=m;i++) dp[root][i]=w[root];
DP方程的主要变化就是dp[i][j-k] -> dp[i][j-k-e.cost]，这里之所以要减去e.cost，是为了防止cost的重复计算。
不妨设k=j-e.cost，你就会发现在计算dp[i][0]，这也是为什么要推cost=0这个状态。
#include "cstdio"#include "iostream"#include "cstring"using namespace std;#define maxn 300struct Edge{ int to,next,c;}e[maxn*2];int w[maxn],num[maxn],dp[maxn][maxn],head[maxn],tol;int n,m,k,u,v,c;void addedge(int u,int v,int c){ e[tol].to=v; e[tol].next=head[u]; e[tol].c=c; head[u]=tol++;}void dfs(int root,int pre){ for(int i=0;i<=m;i++) dp[root][i]=w[root]; int i=root; for(int a=head[root];a!=-1;a=e[a].next) { int t=e[a].to; if(t==pre) continue; dfs(t,root); for(int j=m;j>=0;j--) for(int k=0;k<=j-e[a].c;k++) dp[i][j]=max(dp[i][j],dp[i][j-k-e[a].c]+dp[t][k]); }}int main(){ //freopen("in.txt","r",stdin); while(~scanf("%d",&n)) { memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); tol=0; for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&c); addedge(u,v,c); addedge(v,u,c); } scanf("%d%d",&k,&m); m/=2; dfs(k,k); printf("%d\n",dp[k][m]); }}
| 2875311 | neopenx | ZOJ | 3626 | Accepted | 636 | 0 | C++ (g++ 4.4.5) | 1174 | 2014-10-22 09:13:13 |
ZOJ 3626(树形DP+背包+边cost)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。