第一眼看上去,这道题一点都不套路
第二眼看上去,大概是要考dpdpdp优化,那没事了,除非前面333道题都做完了否则直接做这道题肯定很亏
首先我们要定义一个好的状态。废话
设fsf_{s}fs表示BBB序列的和为sss时,能达到的AAA序列的最大长度,也就是最紧的限制。
这一步定义非常自然,到这里都没有任何问题
不过直接暴力转移复杂度O(S2logn)O(S^2\log n)O(S2logn),考场上好像只能得到20pts20pts20pts。
似乎有根号乱搞的做法,但是这道题nnn,SSS比较大所以会被卡掉
这是逼着我们想正解啊
不管了,根号乱搞比较好想,而且确实也是考场上性价比最高的做法
cdq\text{cdq}cdq分治的想法挺阳间的,应该可以学一下
乱胡一下吧,不过考场上可能我也不会写 考虑计算区间[l,r][l,r][l,r]的dpdpdp值,显然我们知道转移的这个数不会超过[l,r][l,r][l,r]这个区间的长度。
发挥bot\text{bot}bot的能力 我们有转移式fs=maxx≤snxt(fs−x,x)f_s=\max_{x\le s}\text{nxt}(f_{s-x},x)fs=maxx≤snxt(fs−x,x),并且fsf_sfs是单增的,因此∀i∈[mid+1,r],fi>fmid\forall i\in [mid+1,r],f_i>f_{mid}∀i∈[mid+1,r],fi>fmid。先枚举一个xxx,则我们只需要考虑可能对右区间有贡献的sss,即满足nxt(fs,x)=nxt(fmid,x)\text{nxt}(f_{s},x)=\text{nxt}(f_{mid},x)nxt(fs,x)=nxt(fmid,x)。不难猜想,这些sss 形成了一个区间,并且这个区间的左端点就是最小的iii满足fi≥front(fmid,x)f_i\ge \text{front}(f_{mid},x)fi≥front(fmid,x),于是对于这个区间,贡献是相同的,而对应的右半部分下标是连续的,因此用一个线段树维护即可。
复杂度两个log\loglog。应该可以通过吧?
代码先咕了