做了Ural 1513,由于懒得写高精度，所以还是WA,不过这个递推是经过了思考的，思路如下，用一个二维数组来记录在长度为i时的可能情况数，这样的话，如果i<=k那么我们就不用顾忌，dp[i,'L']=dp[i-1,'L']+dp[i-1,'B'] and dp[i,'B']=dp[i-1,'L']+dp[i-1,'B'], 一旦i>k,那么dp[i,'L']=dp[i-1,'L']+dp[i-1,'B']-dp[i-k-1,'B'],也就是说，在累加所有上一个长度可能情况的同时，我们只需要排除从i到i-k都为L而i-k-1位置为B的情况(有待完善。。。)
没有评论:
发表评论