树状DP （poj 2342）

题意：给出N各节点的快乐指数，以及父子关系，求最大快乐指数和（没人职员愿意跟直接上司一起玩）；

思路：从底向上的树状DP；

　　　第一种情况：第i个员工不参与，F[i][0] += max(F[k][1], F[k][0]);(k为i的儿子)

　　　第二种情况：第i个员工参与，F[i][1] += F[k][0];

　　　F[i][j]表示第i个员工是否参与；

　　　边界：F[i][0] = 0；F[i][1] = 其快乐指数；

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#define c_false ios_base::sync_with_stdio(false); cin.tie(0)

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3f

#define zero_(x,y) memset(x , y , sizeof(x))

#define zero(x) memset(x , 0 , sizeof(x))

#define MAX(x) memset(x , 0x3f ,sizeof(x))

#define swa(x,y) {LL s;s=x;x=y;y=s;}

using namespace std ;

#define N 6005

const double PI = acos(-1.0);

typedef long long LL ;

int n,root,ri[N],F[N][],son[N],bro[N];

bool is_son[N];

void init(){

    int i,j,k;

    scanf("%d",&n);

    for(i = ; i <=n; i++) scanf("%d",ri+i);

    zero(son);

    zero(is_son);

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

        scanf("%d%d",&j,&k);

        bro[j] = son[k];son[k] = j;

        is_son[j] = true;

    }

    for(i = ; i <=n ;i++)if(!is_son[i])

        root = i;

}

inline int max(int x,int y){return (x>y)?(x):(y);}

void DP(int u){

    int v;

    F[u][] = ;F[u][]= ri[u];

    for(v= son[u]; v; v= bro[v]){

        DP(v);

        F[u][] += max(F[v][], F[v][]);

        F[u][] +=F[v][];

    }

}

void solve(){

    DP(root);

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

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    //ios_base::sync_with_stdio(false); cin.tie(0);

    init();

    solve();

    return ;

}

秒客网

树状DP （poj 2342）

相关文章