//树形DP
//没有上司的舞会
//树形DP先确定各个子树,再递归返回根,整个过程相当于树的后序遍历
//本题用vetor模拟树的父子关系
//vector[i]里存放以i为父节点的所有子节点
//状态转移方程:
//如果该节点不选:dp[root][0] += max(dp[tree[root][i]][1],dp[tree[root][i]][0]);
//如果选取该节点:dp[root][1] += dp[tree[root][i]][0] ;
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std ;
#define MAX 6005
int hap[MAX] , f[MAX] , dp[MAX][2] ;
vector<int> tree[MAX];void DFS(int root)
{int len = tree[root].size();dp[root][1] = hap[root] ;for(int i = 0 ; i < len ; i ++){DFS(tree[root][i]);}for(int i = 0 ; i < len ; i ++){dp[root][0] += max(dp[tree[root][i]][1],dp[tree[root][i]][0]);dp[root][1] += dp[tree[root][i]][0] ;}
}
int main()
{int n , a , b ;while(scanf("%d" , & n ) != EOF){for(int i = 1 ; i <
详细解决方案
HDU1520-树形DP
热度:72 发布时间:2024-01-18 01:09:01.0
相关解决方案