2012-10-27 07:54:29Morris
[ZJ][dp] a564. ITSA201205 P4 Group without direct leaders
內容 ：
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
範例輸出 ：
90
提示
：
出處
：
(管理：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;
}
樹形 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;
}