题目描述
在满足每个参加舞会人员都没有直接上司的方案中最大的快乐指数.
样例
输入样例:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出样例:
5
树形dp
解题思路
职员和上司的关系构成树形图.
dp
状态定义:
dp[u][0]/dp[u][1]
集合:以u为根的子树且不选u/选u的符合条件的所有人员安排方案.
属性:Max
举例:
dp[4][0]
集合:{ {},{6},{7},{6,7} }
属性:2
状态划分:
树形dp的求解过程类似于记忆化搜索,求解思路:递归求解,先求解u的儿子结点,再求u.
对于dp[u][0],其儿子也就是其直接下属可参加可不参加:dp[u][0] = sum( max(dp[si][0],dp[si][1])
si为u的儿子结点.
对于dp[u][1],u参加其为符合条件其直接下属不能参加.dp[u][1] = sum( dp[si][0] )
时间复杂度
每个结点都会计算一次,每个结点只有两个状态.时间复杂度O(n)
C++ 代码
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Max_N = 6010;
int n;
int happy[Max_N];//快乐指数
int h[Max_N], e[Max_N], ne[Max_N], idx; //邻接表存储树
int dp[Max_N][2]; //状态
bool has_father[Max_N]; //没有父亲的就是根结点 从根开始递归
void add( int u, int v)
{
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void dfs( int u )
{
dp[u][1] = happy[u]; //选择u
for( int i = h[u]; i!=-1; i = ne[i] )
{//遍历儿子
int s = e[i];
dfs(s);
dp[u][1] += dp[s][0];
dp[u][0] += max( dp[s][0], dp[s][1] );
}
}
int main()
{
cin >> n;
for( int i = 1; i<=n; i++ ) cin >> happy[i];
memset(h,-1,sizeof h);//!!
for( int i = 1; i<n; i++ )
{
int s, u;
cin >> s >> u;
has_father[s] = true;
add(u,s);//u->s
}
int root;
for( int i = 1; i<=n; i++ )
{
if( has_father[i]==false )
{
root = i;
break;
}
}
dfs(root);
cout << max( dp[root][0], dp[root][1] ) << endl;
return 0;
}