題目
Ural大學(xué)有N名職員，編號(hào)為1~N。
他們的關(guān)系就像—棵以校長為根的樹，父節(jié)點(diǎn)就是子節(jié)點(diǎn)的直接上司。每個(gè)職員有一個(gè)快樂指數(shù)，用整數(shù)H給出，其中1≤i≤N。
現(xiàn)在要召開一場周年慶宴會(huì)，不過，沒有職員愿意和直接上司一起參會(huì)。
在滿足這個(gè)條件的前提下，主辦方希望邀請(qǐng)一部分職員參會(huì)，使得所有參會(huì)職員的快樂指數(shù)總和最大，求這個(gè)最大值。
輸入格式
第一行一個(gè)整數(shù)N。
接下來N行，第i行表示i號(hào)職員的快樂指數(shù)H;。
接下來N-1行，每行輸入—對(duì)整數(shù)L,K,表示K是L的直接上司。最后一行輸入0,0。
輸出格式
輸出最大的快樂指數(shù)。
數(shù)據(jù)范圍
1<N<6000,—128<Hi≤127文章來源：http://www.zghlxwxcb.cn/news/detail-613371.html
- 輸入樣例:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
- 輸出樣例:
5
題解
import java.util.Arrays;
import java.util.Scanner;
/**
* @author akuya
* @create 2023-07-28-21:52
*/
public class ball {
static int N=6010;
static int n;
static int happy[]=new int[N];
static int h[]=new int[N];
static int e[]=new int[N];
static int ne[]=new int[N];
static int idx;
static int f[][]=new int[N][2];
static boolean has_father[]=new boolean[N];
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();
for(int i=1;i<=n;i++)happy[i]=scanner.nextInt();
Arrays.fill(h,-1);
for(int i=0;i<n-1;i++){
int a,b;
a=scanner.nextInt();
b=scanner.nextInt();
has_father[a]=true;
add(b,a);
}
int root=1;
while(has_father[root])root++;
dfs(root);
System.out.println(Math.max(f[root][0],f[root][1]));
}
public static void add(int a,int b){
e[idx]=b; ne[idx]=h[a];h[a]=idx++;
}
public static void dfs(int u){
f[u][1]=happy[u];
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j);
f[u][0]+=Math.max(f[j][0],f[j][1]);
f[u][1]+=f[j][0];
}
}
}
思路
本題為樹形動(dòng)態(tài)規(guī)劃，思路如下圖
動(dòng)態(tài)轉(zhuǎn)移方程如上圖，結(jié)合之前學(xué)習(xí)的靜態(tài)鏈表即可完成。文章來源地址http://www.zghlxwxcb.cn/news/detail-613371.html
到了這里，關(guān)于Acwing.285 沒有上司的舞會(huì)(動(dòng)態(tài)規(guī)劃)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
