首页 > 代码库 > POJ_2342_树状dp

POJ_2342_树状dp

http://poj.org/problem?id=2342

 

第一道树状dp,入门题,用vector构建有向图。

#include<iostream>#include<cstring>#include<cstdio>#include<vector>using namespace std;int happy[6050],last[6050],dp[6050][2];vector<int> v[6050];vector<int>::iterator it;void dfs(int now){    dp[now][1] = happy[now];    int len = v[now].size();    for(int i = 0;i < len;i++)  dfs(v[now][i]);    for(int i = 0;i < len;i++)    {        dp[now][1] += dp[v[now][i]][0];        dp[now][0] += max(dp[v[now][i]][0],dp[v[now][i]][1]);    }}int main(){    int n;    while(~scanf("%d",&n))    {        memset(dp,0,sizeof(dp));        memset(last,-1,sizeof(last));        for(int i = 1;i <= n;i++)   scanf("%d",&happy[i]);        int a,b;        while(scanf("%d%d",&a,&b) && a && b)        {            v[b].push_back(a);            last[a] = b;        }        a = 1;        while(last[a] != -1)    a = last[a];        dfs(a);        printf("%d\n",max(dp[a][0],dp[a][1]));    }    return 0;}

 

POJ_2342_树状dp