寒假第七次训练-动态规划

F - 树形DP

题目大意：举办一个party，邀请若干人参加，每个人都不愿意和直接上司一同出席（太过扫兴），每个人自身带有活跃值，设计一个邀请方案使得party的总活跃值最大，不存在环。

解题思路：用树形dp解决。若a为b的直接上司，那么dp[a][0]表示a不出席，dp[a][1]表示a出席

a不来时: dp[a][0]+=max(dp[b][1]，dp[b][0])
a来时 ： dp[a][1]=dp[b][0]

AC代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
#define maxn 6005
int n;
int dp[maxn][2],father[maxn];
void tree_dp(int node)
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(father[i] == node)
        {
            tree_dp(i);
            dp[node][1] += dp[i][0];
            dp[node][0] +=max(dp[i][1],dp[i][0]);
        }
    }
}
int main()
{
    int i;
    int f,c,root;
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(father,0,sizeof(father));
        for(i=1; i<=n; i++)
        {
            scanf("%d",&dp[i][1]);
        }
        root = 0;
        bool beg = 1;
        while (scanf("%d %d",&c,&f),c||f)
        {
            father[c] = f;
            if( root == c || beg )
            {
                root = f;
            }
        }
        while(father[root])
            root=father[root];
        tree_dp(root);
        int imax=max(dp[root][0],dp[root][1]);
        printf("%d\n",imax);
    }
    return 0;
}