| 题目名称 | 613. 火车站饭店 |
|---|---|
| 输入输出 | profitz.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2011-11-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：214， 提交：347， 通过率：61.67% | ||||
 LGLJ |
100 | 0.040 s | 11.96 MiB | C++ |
 沐灵_hh |
100 | 0.076 s | 2.69 MiB | C++ |
 lihaoze |
100 | 0.082 s | 7.35 MiB | C++ |
 HeHe |
100 | 0.091 s | 2.69 MiB | C++ |
 AntiLeaf |
100 | 0.121 s | 3.59 MiB | C++ |
 Heaven |
100 | 0.126 s | 3.36 MiB | C++ |
 fmxdd |
100 | 0.127 s | 3.08 MiB | C++ |
 zht |
100 | 0.134 s | 3.46 MiB | C++ |
|
zht |
100 | 0.144 s | 3.46 MiB | C++ |
 海阔天空 |
100 | 0.150 s | 17.47 MiB | C++ |
| 本题关联比赛 | |||
| 20111109 | |||
| 20111109 | |||
| 20151026 | |||
| 20151026 | |||
| 2009noip模拟试卷 | |||
| 树形动态规划 | |||
| 树形动态规划 | |||
| 关于 火车站饭店 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
牛逼！！！
 牛掰格拉斯
2019-10-10 21:53
20楼
| ||||
|
| ||||
|
| ||||
|
听我同桌说要转二叉树
然后我tm卡了二十分钟   Hzoi_Mafia
2017-05-25 11:07
17楼
| ||||
|
数组开小了。。。。。。。
智障一样既T又RE的。。。。。。。 | ||||
|
定义f[s][1]是选择i结点后s结点的子树的最优解，f[s][0]是不选择s结点后i结点的子树的最优解；
状态转移方程 f[s][1] += f[t][0]; f[s][0] += max(f[t][0], f[t][1]); | ||||
|
mdzz f[u][0] 写成 f[i][0]调半小时》。。
| ||||
|
树的最大独立集。。。白书上有，稍微改一改就好了。
蒟蒻rank2 顺便问一句神犇，邻接表的next放结构体里与单独开个next数组，哪个快一些？ | ||||
|
%%%
Janis
2016-10-30 15:53
12楼
| ||||
kZime
sxysxy
Bravo ChaoS【题目描述】
政府邀请了你在火车站开饭店，但不允许同时在两个相连的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有 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