（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>的全部内容，希望文章能够帮你解决（cogs 613 火车站饭店）<树形DP>所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。