Description 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. 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表示人數(shù)。接下來(lái)的N行表示1~N的權(quán)重。接下來(lái)的N-1行每行輸入K L，表示L是K的直屬上司。要求不讓上司和他的下屬一起參加聚會(huì)并且要求權(quán)重達(dá)到最大。 問(wèn)題分析 該問(wèn)題是一個(gè)樹(shù)形DP問(wèn)題。 我們從每一個(gè)節(jié)點(diǎn)出發(fā)考慮這個(gè)問(wèn)題，每一個(gè)人只有參加聚會(huì)或者不參加聚會(huì)這兩種情況，只要取這兩種情況下權(quán)重之和的最大值，幾位最終結(jié)果。 假設(shè)已經(jīng)實(shí)現(xiàn)函數(shù)int get_dp(int root,int i)i取0或1表示標(biāo)號(hào)為root的職員有沒(méi)有參加聚會(huì)，返回他參加聚會(huì)和不參加聚會(huì)的情況下的最大權(quán)重。注：root為當(dāng)前子樹(shù)內(nèi)的最高級(jí)員工。所以我們只要求的最高級(jí)員工在與不在的權(quán)重并取最大值即為最終結(jié)果。 函數(shù)實(shí)現(xiàn)： i==0,root沒(méi)有參加聚會(huì)，則他的直屬員工有可能參加或者有可能不參加，計(jì)算每一個(gè)孩子節(jié)點(diǎn)參加或者不參加聚會(huì)的權(quán)重，并取最大值，累計(jì)到dp[root][0]中。 i==1，root參加了聚會(huì)，則他的直屬員工都沒(méi)有參加聚會(huì)，計(jì)算每個(gè)孩子節(jié)點(diǎn)沒(méi)有參加聚會(huì)的權(quán)重，累計(jì)到dp[root][1]中，并加上自身的權(quán)重。 代碼實(shí)現(xiàn)
#include<iostream>#include<vector>#include<cstdio>#include<algorithm>using namespace std;int dp[6002][2];vector< vector<int> > vec;int w[6002];int get_dp(int root,int i){ if(dp[root][i]!=-1)return dp[root][i]; if(vec[root].size()==1&&i==0){ return 0; } else if(vec[root].size()==1&&i==1){ return 1; } if(i==0){ int temp=0; for(int j=1;j<vec[root].size();j++) temp+=max(get_dp(vec[root][j],0),get_dp(vec[root][j],1)); dp[root][i]=temp; return dp[root][i]; } else if(i==1){ dp[root][i]=w[root]; for(int j=1;j<vec[root].size();j++) dp[root][i]+=get_dp(vec[root][j],0); return dp[root][i]; }}int main(){ int N; scanf("%d",&N); for(int i=1;i<N+1;i++){ scanf("%d",&w[i]); vec.push_back(vector<int>(1,0)); dp[i][0]=-1; dp[i][1]=-1; } vec.push_back(vector<int>(1,0)); for(int i=1;i<N;i++){ int L,K; scanf("%d %d",&L,&K); if(vec[L][0]==0)vec[L][0]=1; vec[K].push_back(L); } int k; for( k=1;k<N+1;k++) if(vec[k][0]==0)break; int result=max(get_dp(k,0),get_dp(k,1)); printf("%d/n",result); return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
