題目鏈接
思考
首先本題中的關系是一種樹形結構，而且符號最優子結構和無后效性，所以可以進行記憶化搜索。
那么首先要在這顆樹中選出一個點作為根節點，按照習慣我們將沒有父節點的點作為根節點。
接下來要思考的是 ?狀態：
dp[i][0]表示不選i時，以i為根子樹的最大權值。
dp[i][1]表示選i時，以i為根子樹的最大權值。
dp[i][0]+=max(dp[j][0],dp[j][1])
dp[i][1]+=dp[j][0]
j是i的兒子，所以首先要dfs到子葉，最后輸出的時候 比較一下 max(dp[i][1],dp[i][0])
?
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 vector<int>G[10005]; 8 int father[10005],dp[10005][3],a[10005],n; 9 10 void dfs(int k){ 11 for(int i=0;i < G[k].size();i++){ 12 int h = G[k][i]; 13 dfs(h); 14 dp[k][0] += max(dp[h][1],dp[h][0]); 15 dp[k][1] += dp[h][0]; 16 } 17 dp[k][1]+=a[k]; 18 } 19 int main(){ 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++){ 22 scanf("%d",&a[i]); 23 } 24 for(int i=1;i<=n;i++){ 25 int x,y; 26 scanf("%d%d",&x,&y); 27 if(!x && !y) break; 28 G[y].push_back(x); 29 father[x] = y; 30 } 31 for(int i=1;i<=n;i++){ 32 if(!father[i]){ 33 dfs(i); 34 printf("%d",max(dp[i][0],dp[i][1])); 35 break; 36 } 37 } 38 return 0; 39 }
?
)
