当前位置: 首页 > news >正文

树形dp [JOI Open 2020] 发电站 / Power Plant

作为最强摸鱼人的 BaiBaiShaFeng,这个题解也是发到洛谷上了,希望给过。

先辈们说的太简略了我感觉有点难懂,虽然我的表达能力很弱,估计强不了多少。

注:参考过网上零散题解。

题意很好理解,我们就不过多叙述了。

不看炸掉的机子,我们实际上是在选择一个联通块去覆盖树的一部分,而我们所要求的就是这个联通块的最大值。

我们统一在这个联通快的最高点进行答案的统计,从子树的贡献向上递归,这个样子问题可以从子树中合并上来,进而考虑树形 dp。

\(dp[u]\) 表示联通块的最高点还在祖先处时 \(u\) 子树中的答案,形象的说,就是上不封顶。

这个时候我们只要选择了 \(u\) 子树中的发电机 \(u\) 自然会炸,因为最高点在祖先,上边会有其他启动的发电机。

所以我们一共有两种决策:选择所有子树中的最佳情况或者干脆不选子树,去选 \(u\) 上的发电机。

注意如果没有发电机便只有第一种情况。

明显不存在其他情况。

转移于是乎就明显起来了,我们在 \(\sum_{v\in son[u]} dp[v]-1\)\(1\) 之间取最大就是 \(dp[u]\) 了。

这个式子对应了我们上边说的两种情况,下边说说答案的统计。

我们规定了在最高点统计答案,每个点都可以是最高点,对于一个最高点,若不想让这个点炸只能选择一个子树中的答案,若允许它炸就直接选择所有子树中的答案再让它炸,第二种和 \(dp[u]\) 最终的结果应该是相等的,但是含义并不一样,后边为了方便写在一起了。

代码如下,这个题想起来有些麻烦但实现起来就很轻松。

#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
struct Node{int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){node[++tottt].to=v;node[tottt].nxt=head[u];head[u]=tottt; return;
}
//以上是平平无奇的存图
int n, dp[MN], has[MN], ans=0;//has表示介个点有没有发电机
void Read(){memset(dp,0,sizeof(dp)); memset(has,false,sizeof(dp));cin>>n;for(int i=1,u,v; i<n; ++i){cin>>u>>v; insert(u,v); insert(v,u);}string s; cin>>s; s=' '+s;for(int i=1; i<=n; ++i){if(s[i]=='1') has[i]=true;}
}
void dfs(int u, int father){for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;dfs(v,u); dp[u]+=dp[v];ans=max(ans,dp[v]+(has[u]));//最高点不炸,选择一棵子树}if(has[u]) dp[u]=max(dp[u]-1,1);ans=max(ans,dp[u]);//最高点可炸
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);Read(); dfs(1,1); cout<<ans<<'\n';return 0;
}

若有不足请告诉我,谢谢啦。

http://www.hskmm.com/?act=detail&tid=21063

相关文章:

  • 深入解析:灵画-AI绘画小程序
  • AT_arc156_b [ARC156B] Mex on Blackboard
  • 产品排序
  • 环形链表II-leetcode
  • ubuntu20.04安装nvidia显卡
  • [线段树系列 #6] 标记永久化
  • 9.29
  • c语言switch和if语句
  • Qt(制作一个方便的文本编辑器)
  • Java EE初阶启程记05---线程安全 - 指南
  • DataGridView表格控件使用说明
  • 题解:P7126 [Ynoi2008] rdCcot
  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题
  • 【还未找到原题】宝石(GEM) - Harvey
  • 第八篇
  • C# AStar 算法 - 实际应用
  • nocobase 源码安装
  • 航司网站url后缀参数FECU分析
  • 子网掩码完全指南:从入门到精通
  • 微信群机器人API
  • 9月29号
  • 【CF19E】Fairy - Harvey
  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践
  • 软件工程中线性回归应用
  • 解决秒杀高并发的一些方案
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网