图论dp实践：暴力与滚动数组解分层图问题

本文档是一篇关于图论和动态规划的教程，针对的是IT学习者，特别是编程新手。作者以“蒟蒻の图论刷题(更新中)Ⅰ - 树/图dp”为名，分享了自己在处理一些比赛题目中的经验，这些题目主要来自中国青少年在线创新竞赛（如TJOI和ZJOI）。其中，重点讨论了一个名为“可乐”的问题，这是一道涉及到分层图和矩阵优化的题目。 题目中提到的问题涉及到了状态转移的动态规划方法。选手需要考虑每座城市的三个状态：0代表上一时刻已经在该城市，1表示当前时刻刚到达，2则表示自爆。核心思路是通过维护一个滚动数组，记录每个时刻0状态（即已到达）和1状态（即新到达）的城市总数，以及2状态（自爆）的累计数量。通过这种方式，可以简化计算，避免遍历整个时间线，从而节省时间和空间。 作者提到使用暴力法和滚动数组（也就是常数级别的额外空间）解决了这个问题，这展示了即使面对复杂问题，简单而巧妙的算法设计也能解决问题，同时表达了对于O2（可能是某种优化技术或数据结构）的赞美。 代码部分展示了如何初始化动态规划数组dp，以及如何根据输入数据进行状态转移。通过递推公式，更新dp数组，最终计算出答案。这里的代码片段使用了C++语言，并定义了一些常用宏和常量，如向量g用于存储图的邻接关系，N定义了一个较大的整数，dp数组用于保存状态转移的结果，以及mod用于取模操作。 这篇文档不仅提供了实际问题的解决策略，还包含了解题技巧和代码实现，对于想要提升图论和动态规划技能的IT学习者来说，是非常有价值的参考资料。