nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

poj3061

链接

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

题意

        给定一个长度为n的正数序列,求和大于等于S的最短的子串长度。
        n<1e5 s<1e9

题解

        先考虑一个暴力做法,枚举所有的子串,此做法复杂度,n^2
        然后我们尝试dp,
        dp[i]代表串S[0:i]中以i结尾的和大于等于S的最大起点
        容易证明:dp[i]关于i单调不减
        于是我们的做法出来了,枚举i,对于j我们通过记录决策点，来优化成O(1)
        然后我惊讶的发现此做法竟然就是尺取法。