傳送門
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 T 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
Sample Input
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
Sample Output
5
題意:要求從n個人中選出一些人來參加party,這n個人不能有直接的上下級關系,每個人有他的價值,要求最後獲得的最大的總價值是多少?
基礎的樹形dp吧,我們用dp[i][0]表示i沒有來,用dp[i][1]表示i過來了,那麼狀态轉移方程也是很明顯的,首先上機若果來了,則他的下級一定不會過來,反之,他的下級可以過來或者不過來。
dp[fa][0] += max(dp[G[fa][i]][1] , dp[G[fa][i]][0]);
dp[fa][1] += dp[G[fa][i]][0];
#include<iostream>
#include<stdio.h>
#include<string>
#include<math.h>
#include<queue>
#include<vector>
#include<string.h>
#include<iterator>
using namespace std;
const int inf = 0x3f3f3f3f;
int val[6005];
int fa[6005];
int dp[6005][2];
vector<int> G[6005];
void dfs(int fa) {
for(int i = 0 ; i < G[fa].size() ; i ++) {
int son = G[fa][i] ;
dfs(son) ;
}
for(int i = 0 ; i < G[fa].size() ; i ++) {
dp[fa][0] += max(dp[G[fa][i]][1] , dp[G[fa][i]][0]);
dp[fa][1] += dp[G[fa][i]][0];
}
}
int main()
{
int n ;
while(~scanf("%d" , &n)) {
memset(fa , 0 , sizeof(fa));
memset(dp , 0 , sizeof(dp));
for(int i = 0 ; i <= n ; i ++)
G[i].clear();
for(int i = 1 ; i <= n ; i ++) {
scanf("%d" , &val[i]);
fa[i] = i;
dp[i][1] = val[i];
}
int u , v ;
while(1){
scanf("%d%d" , &u , &v) ;
if(u == 0 && v == 0)
break;
G[v].push_back(u);
fa[u] = v ;
}
int root = 1;
while(fa[root] != root)
root = fa[root] ;
dfs(root);
cout<<max(dp[root][0] , dp[root][1])<<endl;
}
return 0;
}