Avin is studying series. A series is called "wave" if the following conditions are satisfied:
1) It contains at least two elements;
2) All elements at odd positions are the same;
3) All elements at even positions are the same;
4) Elements at odd positions are NOT the same as the elements at even positions.
You are given a series with length n. Avin asks you to find the longest "wave" subseries. A subseries is a subsequence of a series.

Input

The first line contains two numbers n, c (1 ≤ n ≤ 100, 000, 1 ≤ c ≤ 100). The second line contains n integers whose range is [1, c], which represents the series. It is guaranteed that there is always a "wave" subseries.

Output

Print the length of the longest "wave" subseries.

Sample Input

5 3 1 2 1 3 2

Sample Output

4

题目大意:给你一段序列,要求让你从中找出一段序列满足,奇数位与奇数位相同,偶数位与偶数位相同,奇数位与偶数位不同的一段序列,求其最长长度.

题目思路:这个题我们根据C的范围看出应该是个暴力  C(100,2) 在1e4左右.然后我们对每一种情况判断一下可以不可以,假设我们选定 1 2 这个组合 怎么计算出 1 2 构成的最长序列长度呢,我们首先让1 作为第一个位置,然后2作为第二个位置,什么时候结束呢?当2后面没有1,或者1后面没有2的时候结束.所以这就需要一个辅助结构-----序列自动机,他可以记录 字符后下一个字符的位置,比如说 nex[2][1] 意思就是2后面第一个1所在的位置.所以我们把序列自动机一列:

预处理:  复杂度 n*m 

void restart()
{
    for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++)
            nex[i][k]=-1;
    for(int i=n;i>=2;i--)
    {
        for(int k=1;k<=m;k++) nex[i-1][k]=nex[i][k];//前一个数与当前数对应的一个位置一定相同除了自己
        nex[i-1][num[i]]=i;//包括自己
    }
}

然后有了这个数组之后,我们还需要知道 第一个数据出现的位置.然后while开始循环跑就可以了.

但交过一发之后T了,原因是 C(100,2)可以再优化,我们先对每个数出现的次数进行由小到大排序,如果当前 枚举的两个数次数 加起来还不如现在最优解大,那就直接跳过就可以了(因为不可能产生贡献),否则while跑一遍,更新最长长度,还有一点需要注意,枚举无顺序,其实应该 让1作为第一个位置时 2也得作为第一个位置,都试一遍然后取最长长度,就是1 2 可产生的最长长度.比如说 1 2 1  2就是2,1就是3

优化之后,刚好卡过.

好的直接附上AC代码:

/*
842MS	41700K
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13+5;
const int maxn=1e5+8;
ll n,m;
int nex[maxn][101];
int cot[101];
int first[101];
ll num[maxn];
struct node{
    int cot;
    int id;
}s[101];
void restart()
{
    for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++)
            nex[i][k]=-1;
    for(int i=n;i>=2;i--)
    {
        for(int k=1;k<=m;k++) nex[i-1][k]=nex[i][k];
        nex[i-1][num[i]]=i;
    }
}
bool cmp(node a,node b)
{
    return a.cot>b.cot;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
        s[i].cot=0;
    for(int i=1;i<=n;i++) {
        scanf("%lld",&num[i]);
        if(!s[num[i]].cot) first[num[i]]=i;
        s[num[i]].cot++;
        s[num[i]].id=num[i];
    }
    restart();
    sort(s+1,s+1+m,cmp);
    ll maxl=0;
    for(int i=1;i<=m;i++)
    {
        for(int k=i+1;k<=m;k++)
        {
            if(s[i].cot&&s[k].cot)
            {
                if(s[i].cot+s[k].cot<maxl) continue;
                ll x=0,len=1;int z=first[s[i].id];
                while(1)
                {
                    if(x%2==0)
                        z=nex[z][s[k].id];
                    else
                        z=nex[z][s[i].id];
                    if(z==-1) break;
                    len++;
                    x++;
                }
                maxl=max(maxl,len);
                x=0,len=1,z=first[s[k].id];
                while(1)
                {
                    if(x%2==0)
                        z=nex[z][s[i].id];
                    else
                        z=nex[z][s[k].id];
                    if(z==-1) break;
                    len++;
                    x++;
                }
                maxl=max(maxl,len);
            }
        }
    }
    printf("%lld\n",maxl);
    return 0;
}

总结:学到了新知识,序列自动机,继续加油!