8248: BZOJ4248:AAQQZ

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

IOI2015将要在哈萨克斯坦举行。哈萨克斯坦的“哈萨克”是用字母的“QAZAQ”拼写的。这个“QAZQA”是回文— —知晓这一点的JOI君出于对回文的喜爱,准备用眼前的字符串制作一个回文。JOI君找到了一个长为N的字符串S=( S1,S2,...,SN),每个字符可以用1...C之间的一个整数来表示。从这个字符串第i个位置到第j个位置的字符串(Si, Si+1,...,Sj)称作子串(i,j)。如果子串(i,j)翻转后和原来相等,即(Si,Si+1,...,Sj)=(Sj,Sj-1,...,Si),则称 子串(i,j)是回文的。JOI君进行如下操作来制造回文: 1.        首先,选择S的一个子串。不妨设选择的子串为T。 2.        将子串T按照升序排序,得到T’ 3.        在S中,用T’替换T,得到S’。我们可以这样描述这三项操作:JOI君选择一个子串(i,j),将Si,Si+1, ...,Sj按升序排序得到T’i,T’i+1,...,T’j,最终得到S’=(S1,S2,...,Si-1,T’i,T’i+1,...,T’j,Sj+1,...,SN) 4.        在这之后,寻找S’中的回文子串 JOI进行如上操作后,想要得到最长的回文子串 现在JOI君将字符串S交给了你,请你输出JOI君进行如上操作后能得到的最长回文子串的长度。


输入格式

第一行两个空格分隔的正整数N和C,分别表示字符串的长度和字符集大小 接下来N行,第i行一个正整数Si,表示字符串S中第i个位置的字符 1<=N<=3000 1<=C<=3000 1<=Si<=C


输出格式

输出一行一个正整数,表示JOI君进行操作后能得到的最长回文子串的长度。


样例输入

12 26
26
17
17
17
1
26
1
17
19
20
1
14

样例输出

8
样例输入中,N=12,C=26,S=(26,17,17,17,1,26,1,17,19,20,1,14)。JOI君可以选择子串(4,8),将其按照升序排列
,得到S’=(26,17,17,1,1,17,17,26,19,20,1,14),这样子串(1,8)就是回文了。这个回文长度为8,是最长可能得
到的回文子串。

提示

没有写明提示


题目来源

JOI 2014~2015 春季training合宿 竞技3 By PoPoQQQ

加入题单

上一题 下一题 算法标签: