树型动态规划_C

1、统计人数

2、没有上司的舞会I

3、没有上司的舞会II

1、统计人数

// sgy 佚名
// 树形动态规划
// problem： 统计人数
#include
using namespace std;
#define ll long long
const int N = 100005;
struct edge{
	int to, next;
}e[N];
int head[N];
int n,cnt;
ll f[N];

inline void makelist(int u,int v){
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

// dfs写法
inline void solve(int i){
	f[i] = 1;
	for(int x = head[i] ; x ; x = e[x].next){
		int to= e[x].to;
		solve(to);
		f[i] += f[to];
	}
}
int main(){
	cin>>n;
	cnt = 0;
	for(int i = 2;i<=n;++i){
		int x;cin>>x;
		makelist(x,i);
	}
	// dfs写法
	solve(1);
	for(int i = 1; i <= n; ++i)cout<

 
 
2、没有上司的舞会I 
 
 
// sgy  
// 树形动态规划
// problem ： 没有上司的舞会I
#include
using namespace std;
#define ll long long
const int N = 100005;
struct edge{
	int to, next;
}e[N];
int head[N];
int n,cnt,v[N];
ll f[N][2];  // 0: 不参加   1:参加

inline void makelist(int u,int v){
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

// dfs写法
inline void solve(int i){
	f[i][1] = v[i];
    f[i][0] = 0;
	for(int x = head[i] ; x ; x = e[x].next){
		int to= e[x].to;
		solve(to);
		f[i][0] += max(f[to][0],f[to][1]);
		f[i][1] += f[to][0];
	}
}
int main(){
	cin>>n;
	for(int i = 0;i>x;
		makelist(x,i);
	}
	for(int i = 1;i<=n;++i)cin>>v[i];
	// dfs写法
	solve(1);
	cout<
 
 
3、没有上司的舞会II 
 
 
// sgy  
// 树形动态规划
// problem ： 没有上司的舞会II
#include
using namespace std;
#define ll long long
const int N = 505;
struct edge{
	int to, next;
}e[N];
int head[N];
int n,m,cnt,v[N];
ll f[N][N][2];  // 0: 不参加   1:参加

inline void makelist(int u,int v){
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

// dfs写法
inline void solve(int i){
	for(int x = head[i] ; x ; x = e[x].next){
		int to= e[x].to;
		solve(to);
		for(int j = m; j >= 0; --j){
			for(int k = 0; k <= j; ++k){
				f[i][j][0] = max(f[i][j][0], f[i][j-k][0] + max(f[to][k][0], f[to][k][1]));
				f[i][j][1] = max(f[i][j][1], f[i][j-k][1] + f[to][k][0]);
			}
		}
	}
	// i 这个人最后要考虑一下，因为之前都是考虑他的下属所带来的快乐值。
	for(int j = m; j ; --j){
		f[i][j][1] = f[i][j-1][1] + v[i];
		f[i][j][0] = f[i][j][0] + 0;
	}
}
int main(){
	cin>>n>>m;
	for(int i = 0;i>x;
		makelist(x,i);
	}
	for(int i = 1;i<=n;++i)cin>>v[i];
	// dfs写法
	solve(1);
	cout<
 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/langs/872762.html

树型动态规划

`发表评论`

`评论列表（0条）`