树状DP （poj 2342）-白红宇

树状DP （poj 2342）

阅读量：4430 次

发布时间：2019-06-07

本文共 1582 字，大约阅读时间需要 5 分钟。

题目：

题意：给出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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #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 6005const double PI = acos(-1.0);typedef long long LL ;int n,root,ri[N],F[N][2],son[N],bro[N];bool is_son[N];void init(){ int i,j,k; scanf("%d",&n); for(i = 1; i <=n; i++) scanf("%d",ri+i); zero(son); zero(is_son); for(i = 1; i < n; i++) { scanf("%d%d",&j,&k); bro[j] = son[k];son[k] = j; is_son[j] = true; } for(i = 1; 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][0] = 0;F[u][1]= ri[u]; for(v= son[u]; v; v= bro[v]){ DP(v); F[u][0] += max(F[v][0], F[v][1]); F[u][1] +=F[v][0]; }}void solve(){ DP(root); printf("%d\n",max(F[root][1],F[root][0]));}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(false); cin.tie(0); init(); solve(); return 0;}