[ZJ][dp] a564. ITSA201205 P4 Group without direct leaders＠Morris' Blog

2012-10-27 07:54:29| 人氣364| 回應1 | 上一篇 | 下一篇

[ZJ][dp] a564. ITSA201205 P4 Group without direct leaders

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

In X company, everyone, except the CEO, has a direct leader. There are n persons in the company and everyone has a unique ID from 0 to n-1. The ID of the CEO is 0, and the ID of any one is larger than the one of his/her direct leader. Besides everyone has a weight which is a positive integer. We want to find a group of weight as large as possible such that no one is the direct leader of any other in the group.

輸入說明：

The input contains three lines. The first line is an integers n, 1<n<=90000, which indicates the number of persons in the company. The second line consists of n integers which are the weights of person 0,1,…, n-1, respectively. The total weight is no more than 100,000,000. In the third line, there are n-1 integers which are the ID of direct leaders of person 1, 2,…, n-1, respectively.

輸出說明：

Output the maximum number of person we can group in one line.

範例輸入：

5
10 20 30 40 50
0 1 1 3

範例輸出：

提示：

出處：

(管理：morris1028)

樹形 dp, 每個父節點有兩種狀態的最佳解, 方法數是否有包函他, 或者是沒有,
有的話, 要加上子節點都沒有的最佳解, 沒有的話, 加上子節點有或沒有的最佳解。

/**********************************************************************************/
/* Problem: a564 "ITSA201205 P4 Group without direct leaders" from               */
/* Language: C (657 Bytes)                                                       */
/* Result: AC(160ms, 1.6MB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2012-10-24 20:23:23                                     */
/**********************************************************************************/

#include <stdio.h>
#define maxN 90000
int main() {
    int n, w[maxN], p[maxN], dp[maxN][2], i; /*0 no 1 yes*/
    while(scanf("%d", &n) == 1) {
        for(i = 0; i < n; i++) {
            scanf("%d", &w[i]);
            dp[i][0] = dp[i][1] = 0;
        }
        for(i = 1; i < n; i++)
            scanf("%d", &p[i]);
        for(i = n-1; i >= 0; i--) {
            dp[i][1] += w[i];
            if(i) {
                dp[p[i]][0] += (dp[i][0] > dp[i][1] ? dp[i][0] : dp[i][1]);
                dp[p[i]][1] += dp[i][0];
            }
        }
        printf("%d\n", dp[0][0] > dp[0][1] ? dp[0][0] : dp[0][1]);
    }
    return 0;
}

我要檢舉

#a564#ITSA201205#P4#Group without direct leaders

台長： Morris

您可能對以下文章有興趣

[ZJ][IDA*] d207. 15 - Puzzle

a129. 最小生成樹

a207. 精準覆蓋問題(Exact cover)

[ZJ][LCA][offline] d767. 血緣關係

人氣(364) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][拓樸排序] a552. 模型
此分類上一篇:[ZJ][bitset] a561. 內存不足

回應(0)