A 读入的时候遍历检查一遍,看有多少个字符 s. B 暴力模拟即可。即 i 从第 n 项到第 0 项,每次 。就可求出 f(x)。复杂度 O(nm)。 C 考虑倒推。如果当前最后一步向右走那么就相当于把这个字符插入到最前面,如果是向左走就相当于插入到最后面。直接用一个 deque 维护一下即可。 D 考虑按照 从小往大排序,考虑 表示前 i 个数,第 i 个数必须选最多能选多少个。转移为: 考虑如何优化转移,我们维护mx[z]表示: 那么, 考虑 mx 和 dp 都可以在 的时间内求得。 考虑 。 所以时间复杂度是 O(nlogn) 的。