首页 > 代码库 > 树形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入门