nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

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映射,
        然后我惊讶的发现此做法竟然就是尺取法。