[luoguP1352] 没有上司的舞会（DP）

传送门

树上的dp，从底向上dp就行。

设dp[u][0]表示不选节点 u 的最大值，dp[u][1]表示选节点 u 的最大值。

则状态转移方程为：

dp[u][0] =∑max(dp[v][1], dp[v][0])

dp[u][1] =∑dp[v][0] + val[u]

（节点v是节点u的孩子）

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define MAXN 12001 5 6 using namespace std; 7 8 int n, cnt; 9 int head[MAXN], to[MAXN], next[MAXN], val[MAXN], f[MAXN], r[MAXN], dp[MAXN][2]; 10 11 inline void add(int x, int y) 12 17 18 inline void dfs(int u) 19 32 } 33 } 34 35 int main() 36 47 for(i = 1; i <= n; i++) 48 if(!r[i]) 49 53 dfs(pos); 54 printf("%d", max(dp[pos][0], dp[pos][1])); 55 return 0; 56 }
View Code

上一篇：[luoguP2420] 让我们异或吧（dfs + 异或的性质）

下一篇：[luoguP2912] [USACO08OCT]牧场散步Pasture Walking（lca）

---

DP