【HDU 1520】 Anniversary Party

【题目链接】

点击打开链接

【算法】

树形DP

令f[i][0]表示：以i为根的子树中，若i不参加宴会，所能获得的最大愉悦值

f[i][1]表示：以i为根的子树中，若i参加宴会，所能获得的最大愉悦值

那么，如果i不参加宴会，它的下属就可以参加宴会，也可以不参加宴会，因此 :

f[i][0] = sigma( max(f[j][0],f[j][1]) ) （j为i的子节点）

如果i参加宴会，它的下属必然不能参加宴会，因此 :

f[i][1] = Ri + sigma( f[j][0] ) (j为i的子节点）

最后，答案为max(f[root][0],f[root][1])（root为根节点）

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 6010

int i,n,u,v,root;

vector<int> e[MAXN];

int val[MAXN],fa[MAXN],f[MAXN][];

inline void dfs(int x)

{

        int i,y;

        f[x][] = val[x];

        for (i = ; i < e[x].size(); i++)

        {

                y = e[x][i];

                dfs(y);

                f[x][] += max(f[y][],f[y][]);

                f[x][] += f[y][];

        }

}

int main()

{

        while (scanf("%d",&n) != EOF)

        {

                for (i = ; i <= n; i++)

                {

                        e[i].clear();

                        f[i][] = f[i][] = ;

                }

                for (i = ; i <= n; i++) scanf("%d",&val[i]);

                for (i = ; i < n; i++)

                {

                        scanf("%d%d",&u,&v);

                        e[v].push_back(u);

                        fa[u] = v;

                }

                scanf("%d%d",&u,&v);

                for (i = ; i <= n; i++)

                {

                        if (!fa[i])

                                root = i;

                }

                dfs(root);

                printf("%d\n",max(f[root][],f[root][]));

        }

        return ;

}

巴特西

【HDU 1520】 Anniversary Party

最新文章

热门文章