[P1514][NOIP2010]引水入城

题解

看到网上很多dfs,bfs,记忆化搜索的代码(其实这个主要也是深搜),但是本校大佬@Ajsoabk用了一个神奇的方法,把它转化成一个线段覆盖的问题。

首先用了一便深搜,如果所有的蓄水池都建了,能不能满足要求,不满足就直接输出,满足说明肯定有解,下一步。

确保了有解之后,我们就可以从每个能建蓄水池的城市出发,走到沙漠城市,能够走到的沙漠城市一定是一段连续的区间(要不然就不会有解),我们求出这些区间,然后统计答案即可

注释说的比较详细了

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注