POJ 2342 Anniversary party - (TYVJ p1052 - wikioi 1380 - 动态规划: 树形dp-没有上司的舞会)

动态规划: 树形dp-没有上司的舞会 | yutian's blog

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests’ conviviality ratings.

Input

Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go N – 1 lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0

Output

Output should contain the maximal sum of guests’ ratings.

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。意思是如果某人直接上司去了，那么他就不去。

输入描述

第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。

输出描述

输出最大的快乐指数。

样例输入

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

样例输出

5

思路

设状态f[k][0],表示k不参加舞会时最大的快乐指数，f[k][1]表示k参加舞会时的最大快乐指数
状态转移方程如下：

$f[k][0]=\sum max \left( f[l][0], f[l][1] \right)$

$f[k][1]=\sum f[l][0] + happy[k]$

树形dp的以大特点就是数据是分好几块的，相互之间并不影响，比如说处理左子树和右子树时，两边的数据是不会相互影响的，即只用到了一部分数据。而一般的dp算法都是从0-n一步一步算出来的。
这两道题目可以说一个类型的，都是在树上选取一些结点，以获得最优值，限制条件就是子节点和父节点的关系，二者不可以都选取，或者不可以都不选取，所以代码几乎都一样。  

https://cloud.tencent.com/developer/article/1108936

http://www.cnblogs.com/qscqesze/p/4134011.html

http://blog.csdn.net/Tc_To_Top/article/details/45021113

对于每个人，都有去和不去两种可能，所以找到根节点，向下处理。
对于每个节点:
 1、如果到场，则在这个点的气氛值 =其所有下属都不到场时的气氛值 +其本身的气氛值。
 2、如果不到场，则在这个点的气氛值=其下属到场（或者不到场，二者取较大值）时的气氛值。

void dp(int k) {
    f[k][1] = happy[k];
    for (int i = 0; i < G[k].size(); i++) {
        int l = G[k][i];
        dp(l);
        f[k][1] += f[l][0];
        f[k][0] += max(f[l][0], f[l][1]);
    }
}

void solve() {
    int i = 0;
    for (i = 1; i <= n; i++) {
        if (!has_boss[i])
            break;
    }
    dp(i);
    cout<<max(f[i][0], f[i][1])<<endl;
}

int main() {
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>happy[i];
    }
    
    int l, k;
    for (int i = 1; i <= n - 1; i++) {
        cin>>l>>k;
        G[k].push_back(l);
        has_boss[l] = 1;
    }
    
    cin>>l>>k;
    
    solve();
}

http://blog.csdn.net/u012350533/article/details/12361895

1. * 分析：用dp[u][1]表示选第u个人时以u为根的子树的最大欢乐度。dp[u][0]表示不选u。 
2. * 又上司不能和下属同选，则有 
3. * dp[u][1]=sigma(dp[v][0])+w[i]{v是u的儿子结点} 
4.  * dp[u][0]=sigma(max(dp[v][0],dp[v][1])){v是u的子结点} 
5. * 边界条件:如果i是叶子，则dp[u][0]=0;dp[u][1]=w[i]; 
6. * 关键：由儿子向父节点转移状态； 

1. inline void addedge(int u,int v)  
2. {  
3.      edge[cnt].v=v;  
4.      edge[cnt].next=head[u];  
5.      head[u]=cnt++;  
6. }  
7.   
8. inline void DFS(int u)  
9. {  
10.      dp[u][1]=w[u];  
11.      dp[u][0]=0;  
12.      for(int i=head[u];i!=-1;i=edge[i].next)  
13.      {  
14.          int v=edge[i].v;  
15.          DFS(v);  
16.          dp[u][1]=max(dp[u][1],dp[v][0]+dp[u][1]);  
17.          dp[u][0]=dp[u][0]+max(dp[v][1],dp[v][0]);  
18.      }  
19. }  
20.   
21. int main()  
22. {  
23.     int n;  
24.      while(scanf("%d",&n)!=EOF)  
25.      {  
26.          for(int i=1;i<=n;i++)  
27.           scanf("%d",&w[i]);  
28.   
29.          cnt=0;  
30.          memset(vis,false,sizeof(vis));  
31.          memset(head,-1,sizeof(head));  
32.          int x,y;  
33.   
34.          for(int i=1;i<n;i++)  
35.          {  
36.              scanf("%d%d",&x,&y);  
37.              vis[x]=true;  
38.              addedge(y,x);  
39.          }  
40.   
41.          scanf("%d%d",&x,&y);  
42.          memset(dp,0,sizeof(dp));  
43.   
44.          for(int i=1;i<=n;i++)  
45.          {  
46.              if(!vis[i])  
47.              {  
48.                  DFS(i);  
49.                  printf("%d\n",max(dp[i][0],dp[i][1]));  
50.                  break;  
51.              }  
52.          }  
53.      }  
54.      return 0;  
55. }  

http://www.cnblogs.com/qscqesze/p/4134011.html

void dfs(int k)//dfs求解
{
    for(int i=0;i<g[k].size();i++)//搜索每一个子节点
    {
        int h=g[k][i];
        dfs(h);
        f[k][0]+=max(f[h][1],f[h][0]);//去或者不去，0表示不去，1表示去
        f[k][1]+=f[h][0];
    }
    f[k][1]+=a[k];
}

int main()
{
        sspeed;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==0&&y==0)
            break;
        g[y].push_back(x);//表示g[y]的子是什么
        b[x]=y;//表示x的父节点
    }//建树过程，用一个vector建树
    for(int i=1;i<=n;i++)
    {
        if(b[i]==0)//从根开始
        {
            dfs(i);
            cout<<max(f[i][0],f[i][1])<<endl;
        }
    }
    return 0;
}

Read full article from 动态规划: 树形dp-没有上司的舞会 | yutian's blog