送分题 题解

· · 题解

Sub 1 是爆搜，Sub 2 是想到贪心策略但是没有预处理串之间，O(n^2)，Sub 3 是给可能有的奇怪的数据结构做法。

可以把题目中的取的方式抽象为 n 个栈，每个栈里依次有所有后缀。

但是这样串长之和就是平方级别的了，所以考虑简化：对于每个串，中间的字符的贡献我们是已经确定的，先提前算好，现在只需要最大化串和串之间的贡献，也就是只有串的开头和结尾的信息有用。这样我们就把串长之和变成线性。且串只有 00 01 10 11 四种。

下面考虑贪心策略，重复执行以下策略直到所有栈为空：

如果当前最后一位是 0，先把 00 都用上，用不了了然后用 01。如果这也没有那么就用 11，如果同时有 10 11 那么先用 11 后面还能用上 10，比直接 10 合适。

如果当前最后一位是 1，先把 11 都用上，用不了了然后用 10。如果这也没有那么就用 00，如果同时有 00 01 那么先用 00 后面还能用上 01，比直接 01 合适。

枚举第一位是 0 还是 1 即可。复杂度 O(n)。