本文主要是介绍（cogs 613 火车站饭店）树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题面
【题目描述】
政府邀请了你在火车站开饭店，但不允许同时在两个相连的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有 50 个和它相连接的火车站。
告诉你每个火车站的利润，问你可以获得的最大利润为多少？
例如下图是火车站网络：
最佳投资方案是 1 ， 2 ， 5 ， 6 这 4 个火车站开饭店可以获得的利润为 90.
【输入格式】
第一行输入整数 N(<=100000), 表示有 N 个火车站，分别用 1,2,……..,N 来编号。接下来 N 行，每行一个整数表示每个站点的利润，接下来 N-1 行描述火车站网络，每行两个整数，表示相连接的两个站点。
【输出格式】
输出一个整数表示可以获得的最大利润。
【样例输入】
6
10
20
25
40
30
30
4 5
4 6
3 4
1 3
2 3
【样例输出】
90
- 由题意知这是一棵树
- 不允许在相邻的火车站开店的意思是任意两个店不能直接相连
- 用f[i]表示选这个点所获得的最大利润，g[i]表示不选这个点所获得的最大利润
- DP方程：
f[u]+=g[v]; 不选子节点
g[u]+=max(g[v],f[v]); 比较利润确定选不选子节点
f[u]+=val[u]; 若选这个点，则加上这个店的利润
这个代码也可以过cogs 190 周年纪念聚会
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int MAXN=100010;
int n;
struct node{int to,next;
}e[MAXN*2];
int head[MAXN],cnt=0;
int val[MAXN];
int f[MAXN],g[MAXN];void add(int f,int t){//邻接表存边cnt++;e[cnt]=(node){t,head[f]};head[f]=cnt;
}void dfs(int u,int fa){for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v!=fa){//判重dfs(v,u);f[u]+=g[v];g[u]+=max(g[v],f[v]);}}f[u]+=val[u];
}int main(){freopen("profitz.in","r",stdin);freopen("profitz.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&val[i]);for(int i=1;i<=n-1;++i){int a,b;scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs(1,1);cout<<max(f[1],g[1]);return 0;
}
这篇关于（cogs 613 火车站饭店）树形DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
