专栏首页数据结构与算法TopcoderSRM679 Div1 250 FiringEmployees(树形dp)

TopcoderSRM679 Div1 250 FiringEmployees(树形dp)

题意

[题目链接]这怎么发链接啊。。。。。

有一个 \(n\) 个点的树,每个点有点权(点权可能为负) ,求包含点\(1\)的最 大权连通子图(的权值和) 。 \(n \leqslant 2500\)

Sol

刚开始还以为是个树形依赖背包呢。。结果发现后面给的两个vector根本就没用

直接减一下得到每个点的点权,然后xjb dp一波

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int a[MAXN], f[MAXN];
vector<int> v[MAXN];
class FiringEmployees{
public:
    void dfs(int x, int fa) {
        f[x] = a[x];
        for(int i = 0, to; i < v[x].size(); i++) {
            if((to = v[x][i]) == fa) continue;
            dfs(to, x);
            f[x] = max(f[x], f[x] + f[to]);
        }
    }
    int fire(vector <int> fa, vector <int> salary, vector <int> productivity) {
        int N = fa.size();
        for(int i = 1; i <= N; i++) {
            a[i] = productivity[i - 1] - salary[i - 1];
            //cout << fa[i - 1] << endl;
            v[fa[i - 1]].push_back(i);

        }
        dfs(0, -1);
        return f[0];
    }
};

int main() {
    int N = read();
    vector<int> a, b, c;
    for(int i = 1; i <= N; i++) a.push_back(read());
    for(int i = 1; i <= N; i++) b.push_back(read());
    for(int i = 1; i <= N; i++) c.push_back(read());
    cout << FiringEmployees().fire(a, b, c);
}
/*
6
0 0 1 1 2 2
1 1 1 2 2 2
2 2 2 1 1 1

9
0 1 2 1 2 3 4 2 3
5 3 6 8 4 2 4 6 7
2 5 7 8 5 3 5 7 9


2
0 1
1 10
5 5

4
{{0, 1, 2, 3}
{4, 3, 2, 1}
{2, 3, 4, 5}}
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • T4701 【卜卜】树状数组模板

    题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

    attack
  • 洛谷P2312 解方程(暴力)

    对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

    attack
  • BZOJ3509: [CodeChef] COUNTARI(生成函数 分块)

    发现 ,那么有一种暴力思路是枚举j,对于之前出现过的数构造一个生成函数,对于之后出现过的数构造一个生成函数,求一下第 项的值。复杂度

    attack
  • T4701 【卜卜】树状数组模板

    题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

    attack
  • 查找(上)

    AngelNH
  • 挑战程序竞赛系列(26):3.5二分图匹配(1)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【每日算法Day 63】LeetCode 第 179 场周赛题解

    https://leetcode-cn.com/problems/generate-a-string-with-characters-that-have-odd...

    godweiyang
  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • P1967 货车运输 未完成

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<c...

    attack
  • LeetCode Contest 180

    ShenduCC

扫码关注云+社区

领取腾讯云代金券