poj3320

链接

http://poj.org/problem?id=3320

题意

一本书有P页，每一页都一个知识点，求去最少的连续页数覆盖所有的知识点。
p<1e6

题解

        先考虑一个暴力做法,枚举所有的方案,此做法复杂度,n^2
        然后我们尝试dp,
        dp[i]代表页数[0:i]中以i结尾的，覆盖了所有的知识点的最大的页数起点
        显然起点j --->  dp[i] j<i
        容易证明:dp[i]关于i单调不减
        加速判断过程，可以map记录，也可以hash映射,
        然后我惊讶的发现此做法竟然就是尺取法。

博主蒟蒻可以随意转载但要附上本文链接广告位招租