首页 > 代码库 > 树形dp入门
树形dp入门
poj2057
某公司的上下级关系是一颗树状结构,每个人不能与他的上司同时出现,每个人有一个值,求最大值。
这个题需要注意的是如果不保存状态会超时,这似乎也是大部分dp应该注意的事情啊
#include<iostream>#include<string.h>#include<stdio.h>#include<vector>using namespace std;const int maxa = 6005;int n;vector< int> xiashu[maxa];int dp[maxa][2];int v[maxa];int du[maxa];int dfs(int x, int zai){ int maxn = 0; int sum = 0; if(dp[x][zai]) return dp[x][zai]; for(int i = 0;i < xiashu[x].size(); i++){ int k = xiashu[x][i]; sum += dfs(k, 0); } maxn = sum; if(zai) return dp[x][zai] = maxn; sum = 0; for(int i = 0; i < xiashu[x].size(); i++){ int k = xiashu[x][i]; sum += dfs(k, 1); } return dp[x][zai] = max(maxn, sum +v[x]);}int main(){ while(scanf("%d", &n)!=EOF){ for(int i = 1;i <= n; i++){ scanf("%d", &v[i]); } memset(dp, 0, sizeof(dp)); memset(du, 0, sizeof(du)); for(int i = 1; i<= n; i++) xiashu[i].clear(); int x, y; while(1){ scanf("%d%d", &x, &y); if(!y && !x) break; xiashu[y].push_back(x); du[x]++; } for(int i = 1; i <= n; i++){ if(du[i]==0) printf("%d\n", dfs(i, 0)); } }}
树形dp入门
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。