QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 512 MB Total points: 100

# 5368. 异世界的文章分割者

Statistics

因无意中惹恼了掌管天空的神祗,作为惩罚,艾德被流放到了异世界。与原来的世界相比,异世界的语言同样是用 $26$ 个小写英文字母来传达信息;但不同之处在于,其信息的表达并不依赖于断句。但如果一个句子包含的信息量过大,则会让人无法接受。具体来说,对于两个字符串 $s_1,s_2$,定义 $w(s_1,s_2)$ 为有多少个不同的字符串是 $s_1,s_2$ 的公共子串,那么对于一个长度为 $m$ 的句子 $t$,设 $t[l, r]$ 表示 $t$ 中第 $l$ 个字符到第 $r$ 个字符组成的字符串,下标从 $1$ 开始,则其包含的信息量为 $$ val(t) = \sum_{i=1}^{m-1} w^2(t[1,i],t[i+1,m]) $$ 好不容易适应异世界生活的艾德,凭借着自己以往的算法学习经历,应聘到了仅在异世界才有的职业——文章分割者。他每天的任务就是把文章分隔成一个个句子。为了保持美观,一篇文章中的句子数量必须恰好为 $k$。艾德要做的就是在满足上述条件下,使信息量最大的句子中包含的信息量尽可能少,以增强文章的可读性。

为了实现逃离异世界的计划,艾德需要去寻找散落在各地的时间碎片。但为了能够继续在异世界生存,他又不能丢掉这份工作,于是他找到了你来帮助他通过每天的任务检查。具体来说,你只需要对每篇文章回答,在使得信息量最大的句子中包含的信息量尽可能少的条件下,分割后所有句子中最大的信息量是多少。

输入格式

第一行包含两个整数 $n,k$,表示文章的长度以及需要划分出的句子数。

第二行包含一个长度为 $n$ 且仅由小写字母组成的文章 $t$。

输出格式

输出一行一个整数表示分割后句子中最大的信息量。

样例数据

样例 1 输入

10 3
ababababab

样例 1 输出

11

样例 2 输入

15 2
abcabcddcbacbad

样例 2 输出

57

子任务

对于所有数据,$1 \leq n \leq 5 \times 10^4, 1 \leq k \leq n$。保证答案不超过 $10^{18}$。

  • Subtask 1(10 pts): $n \leq 10$
  • Subtask 2(10 pts): $n \leq 50$
  • Subtask 3(20 pts): $n \leq 200$
  • Subtask 4(20 pts): $n \leq 1000$
  • Subtask 5(40 pts): No additional constraints.