【题目链接】:http://codeforces.com/problemset/problem/743/E

【题意】



给你n个数字;

这些数字都是1到8范围内的整数;

然后让你从中选出一个最长的子列;

要求这个子列中各个数字出现的次数的差的绝对值都不超过1;

且如果是相同的数字的话：

都是连在一起的(不会有分散的数字);

问你这个最长的序列的长度是多少;

【题解】



二分每个数字至少出现的次数x,(即最少出现x次,当然也可以是x+1次);

(单调性是显然的吧,因为如果每个数字出现5次是可行的话,那么3次肯定也是可以的,二分是正确的);

然后判断这样的序列存不存在;

可以一个数字一个数字的判断;

对于每个数字而言.

只有两种情况.在这个序列中,或者不在;

(想要加入到这个序列中,

则必须之前没有出现过,

因为题目有要求不能出现分散的块;

如果之前没有出现过;

则加入到这个序列中,

枚举它要出现x次,还是x+1次,

则可以写个lower_bound快速判断它之后的

第x个该数字(或是x+1)的位置,然后再从那个位置后一位开始,

继续选择,同时记录刚才那个数字已经加入到序列中;

(同时序列的长度递增x或是x+1)

当然也可以不选这个数字,则往后移动一位;

到了第n+1个位置的时候,看看是不是所有的8个数字都选了;

是的话则返回找到了一个序列,否则返回一个很小的值就好;

这些都用记忆化搜索写吧.

开个

f[i][s],表示当前扫描到第i个位置,当前选择的数字的状态为s;(二进制对应);

的最大序列长度;

bo[i][s]记录这个状态有没有找过.

i最大1000，s最大2^8=256

状态这么少,怎么样都不会超啦;

然后如果能找到x的序列,就尝试把x搞大一点,继续找;

然后x为0的情况没办法在做记搜的时候体现出来;

得自己一开始的时候预处理出ans



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1100;

const int MM = 1<<8;

const int INF = -0x3f3f3f3f;

int n,a[N],mark,ans,f[N][MM+10];

bool bo[N][MM+10];

vector <int> v[10];

int dfs(int i,int s,int x)

{

    if (bo[i][s]) return f[i][s];

    bo[i][s] = true;

    if (i>n)

    {

        if (s==MM-1)

        {

            return f[i][s] = 0;

        }

        else

            return f[i][s] =  INF;

    }

    int ret = INF;

    if (!((s>>(a[i]-1))&1))

    {

        int pos = lower_bound(v[a[i]].begin(),v[a[i]].end(),i)-v[a[i]].begin();

        if (pos+x-1<int(v[a[i]].size()))

        {

            ret = max(ret,x+dfs(v[a[i]][pos+x-1]+1,s|(1<<(a[i]-1)),x));

        }

        if (pos+x<int(v[a[i]].size()))

        {

            ret = max(ret,x+1+dfs(v[a[i]][pos+x]+1,s|(1<<(a[i]-1)),x));

        }

    }

    f[i][s] = max(ret,dfs(i+1,s,x));

    return f[i][s];

}

bool ok(int x)

{

    ms(f,INF);

    ms(bo,0);

    int ret = INF;

    ret = max(ret,dfs(1,0,x));

    ans = max(ans,ret);

    if (ret>=0)

        return 1;

    else

        return 0;

}

int main()

{

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n;

    rep1(i,1,n)

    {

        cin >> a[i];

        if(!((mark>>a[i])&1))

        {

            mark|=(1<<a[i]);

            ans++;

        }

        v[a[i]].pb(i);

    }

    int l = 1,r = n/8;

    while (l<=r)

    {

        int mid = (l+r)>>1;

        if (ok(mid))

            l = mid+1;

        else

            r = mid-1;

    }

    cout << ans << endl;

    return 0;

}