1319: 没有上司的晚会-c++-动规加深搜

解题思路:
这是一道树形DP，可以用深搜和动规来实现

定义dp数组：

int dp[10010][3];//dp[x][0]代表x没来快乐最大值，dp[x][1]代表x来了快乐最大值

定义一个二维数组，储存一个节点的下属

vector g[10010];

深搜主体代码：

void dfs(int x) //当前节点
{
    dp[x][0] = 0;
    dp[x][1] = v[x];//初始化
    for(int i = 0; i < g[x].size(); i++)
    {
        dfs(g[x][i]);//先深搜！！搜索完才可以有数据来递推
        dp[x][0] += max(dp[g[x][i]][0],dp[g[x][i]][1]);//上司没来取最大值
        dp[x][1] += dp[g[x][i]][0];//上司来了下属只能不来
    }
}

还有一个问题，从哪里开始搜索？得找到根节点

根节点没有父节点

用b数组来存储x是否有父节点

int v[10010];

在输入过程中，顺便标记b数组

输入结束后，再遍历找出根节点root

void find_root()
{
    for(int i = 1; i <= n; i++)
    if(b[i] == false)
    {
        root = i;
        break;
    }
}

最后输出root节点的最大值

cout << max(dp[root][0],dp[root][1]) << endl;

参考代码:

#include <bits/stdc++.h>
using namespace std;
int dp[10010][3];
int v[10010];
vector g[10010];
bool b[10010];
int n,root;
void read()
{
    memset(b,false,sizeof(b));
    cin >> n;
    for(int i = 1; i > v[i];
    int x,y;
    while(1)
    {
        cin >> x >> y;
        if(!x && !y) break;
        g[y].push_back(x);
        b[x] = true;
    }
}
void find_root()
{
    for(int i = 1; i <= n; i++)
    if(b[i] == false)
    {
        root = i;
        break;
    }
}
void dfs(int x)
{
    dp[x][0] = 0;
    dp[x][1] = v[x];
    for(int i = 0; i < g[x].size(); i++)
    {
        dfs(g[x][i]);
        dp[x][0] += max(dp[g[x][i]][0],dp[g[x][i]][1]);
        dp[x][1] += dp[g[x][i]][0];
    }
}
int main()
{
    read();
    find_root();
    dfs(root);
    cout << max(dp[root][0],dp[root][1]) << endl;
    return 0;
}