cookiebus 2023-10-11 12:48:16 4 返回题目
考虑到暴力dfs搜索的瓶颈在于我们可能会搜到大量权值小于 x 的序列,所以如果保证我们每次都能搜到满足条件的字符我们就可以O(nk)解决这个问题。
可以设 表示 i 个字符是 j 开始往后最多能得到多少权值。
然后根据 dp 数组暴力 dfs 就好了。
时间复杂度:O(nk)
参考题解:https://www.cnblogs.com/QuantAsk/p/15405016.html