BZOJ4248 JOI15 AAQQZ

제목 의 대의
문자열 집합 [1, C] 의 길이 가 N 인 문자열 S 를 지정 합 니 다. 구간 [L, R] 을 선택 하여 [L, R] 의 문 자 를 작은 것 에서 큰 것 으로 정렬 할 수 있 습 니 다. 그 다음 에 얻 은 가중치 는 현재 S 에서 가장 긴 답장 문자열 의 길이 입 니 다.가장 많은 권력 치 를 얻 을 수 있 느 냐 고 물 었 다.
데이터 범위
1≤C,N≤3000
해제
이 문 제 는 매우 재 미 있 는 것 같 아서 왜 억지로 분류 토론 문제 라 고 말 해 야 하 는 지 모르겠다.먼저, 우 리 는 최종 적 으로 얻 은 가장 긴 답장 문자열 의 답장 센터 를 분류 토론 할 것 이다. 1. 답장 센터 는 정렬 되 지 않 았 다. 2. 답장 센터 는 정렬 된 후에 바 뀌 었 고 접두사 가 존재 하기 때문에 정렬 되 지 않 았 다. 위의 분 류 는 하나의 답장 문자열 이 모두 정렬 된 상황 을 고려 하지 않 았 다. 우 리 는 마지막 으로 S 를 정렬 할 수 있다.통계 해 보면 돼.
그 다음 에 우 리 는 정렬 된 구간 이 모두 오른쪽 에 있 는 것 을 고려 합 니 다. 즉, 답장 문자열 의 앞 에 정렬 하지 않 고 앞 에 정렬 된 상황 에 대해 우 리 는 전체 문자열 을 거꾸로 할 수 있 습 니 다.
답장 센터 가 정렬 되 지 않 았 습 니 다.
먼저 회 문 센터 를 매 거 하여 위치 i i 로 설정 하고 우 회 문 에 대한 상황 은 유사 하 다.생각해 보 세 요. 우 리 는 처음에 반드시 그 가 양쪽 으로 먼저 일치 하도록 하 는 것 이 고, 많이 나 오 는 것 에 대해 서 는 정렬 로 일치 하도록 하 는 것 입 니 다.현재 매우 긴 답장 문자열 을 (L r, R l) (Lr, Rl) 로 설정 하고 정렬 구간 의 오른쪽 점 을 [R r] [Rr] 로 설정 합 니 다. 왼쪽 에 [x, L r] [x, Lr] [x, Lr] 와 일치 하도록 설정 하면 우 리 는 [R l, R r] [Rl, Rr] 에 대해 정렬 해 야 하기 때문에 [x, Lr] 는 단 조 롭 게 줄 어 들 것 입 니 다.따라서 우 리 는 처음에 가장 작은 Ll 을 폭력 적 으로 찾 아 [Ll, Lr] 를 단 조 롭 게 줄 일 수 있 었 다. 그러면 x 는 반드시 이 구간 안에 있 었 다.현재 의 관건 은 [Rl, Rr] 에 대해 대응 하 는 최소 x 를 어떻게 확정 하 느 냐 하 는 것 이다.Cntc, l, r 를 설정 하면 c 문자 가 [l, r] 에 나타 난 횟수 를 표시 합 니 다. 그러면 우 리 는 * 8704 ° icnti, x, Lr ≤ Cnti, Rl, Rr 를 만족 시 켜 야 합 니 다. 그렇지 않 으 면 우 리 는 모 을 수 없습니다.그러나 또 하나의 조건 은 무시 할 수 없다. 즉, 중간 에 끊 으 면 안 된다 는 것 이다. 즉, 8704 ° i < SxCnti, x, Lr = Cnti, Rl, Rr 를 만족 시 키 려 면 i < Sx 가 있어 서 는 안 되 고 Cnti, x, Lr < Cnti, Rl, Rr 를 만족 시 켜 야 한다.
그러면 우 리 는 두 개의 지침 l1, l2 를 설정 할 수 있 습 니 다. 앞 에 가장 작은 x 만족 을 표시 합 니 다. 즉, x, Lr ≤ Cnti, Rl, Rr, 후 자 는 가장 작은 x 만족 은 i < Sx 가 존재 하지 않 는 다 고 표시 합 니 다. 그래서 Cnti, x, Lr < Cnti, Rl, Rr 를 고려 하여 Rr 를 뒤로 이동 하 는 것 은 CntSRr 에 1 을 더 하 는 것 과 같 습 니 다. 그러면 우 리 는 l1 을 앞으로 이동 시 키 고 l2 를 뒤로 이동 하면 됩 니 다.그러나 주의해 야 할 작은 세부 사항 이 있 습 니 다. 만약 에 현재 Lr - x = Rr - Rl, 즉 우리 가 최종 적 으로 밖에서 일치 할 수 있다 면 우 리 는 Fi 를 미리 처리 할 수 있 습 니 다. j 는 i 를 끝으로 j 를 시작 으로 하 는 두 꼬치 가 최대 몇 개의 길이 와 일치 하 는 지 를 표시 할 수 있 습 니 다.
이곳 의 복잡 도 는 O (N2) 다.
텍스트 센터 정렬 됨
정렬 되 지 않 은 가장 큰 위 치 를 Lr 로 설정 하면 다음 문 자 는 반드시 Lr 부터 시작 합 니 다. 첫 번 째 는 SLr 보다 작은 문자 입 니 다. 그림 을 그 려 서 느 낄 수 있 습 니 다.그리고 답장 센터 도 반드시 이 문자 일 것 이다. 왜냐하면 그 는 과 거 를 대칭 해 야 하기 때문이다.다음 방법 은 답문 센터 가 정렬 되 지 않 은 것 과 거의 같다.유일한 세부 사항 은 현재 Rr 로 확장 되 었 고 SRr 가 답장 센터 보다 작 으 면 우 리 는 계속 일치 할 수 없다 는 것 이다. 왜냐하면 이것 은 합 법 적 이지 않 기 때문이다. 만약 같다 면 우 리 는 직접 그 를 중간 에 쑤 셔 넣 으 면 된다.
관건 은 코드 죠?

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 3005;

int F[MAXN][MAXN],S[MAXN],N,C;

void Get_F()
{
    memset(F,0,sizeof F);
    //F[i][j] max(S[i - l + 1..i] = S[j..j + l - 1])
    for(int i = 1;i <= N;i ++)
        for(int j = N;j >= i;j --)
            if (F[i - 1][j + 1] >= 0 && S[i] == S[j]) F[i][j] = F[i - 1][j + 1] + 1;
}

int TreatR(int lr,int cent,int rl)
{
    if (!lr || rl > N) return 0;
    static int Cnt[MAXN],Cur[MAXN],Stack[MAXN][2];
    int top = 0;
    memset(Cnt,0,sizeof Cnt),memset(Cur,0,sizeof Cur);
    for(int u = lr;u;u --)
    {
        ++ Cnt[S[u]];
        if (S[u] >= Stack[top][0]) Stack[++ top][0] = S[u],Stack[top][1] = Cnt[S[u]]; else
            break;
    }
    int MiLen = 0,NeedLen = 0,LimLen = top,tmp = 0;
    for(int rr = rl;rr <= N;rr ++)
    {
        if (S[rr] < cent) break; else
            if (S[rr] == cent) ++ MiLen; else
            {
                ++ Cur[S[rr]];
                if (Cnt[S[rr]] >= Cur[S[rr]])
                {
                    while (NeedLen + 1 <= top)
                    {
                        int val = Stack[NeedLen + 1][0];
                        if (Cur[val] >= Stack[NeedLen + 1][1]) ++ NeedLen; else break;
                    }
                } else
                {
                    while (LimLen)
                    {
                        int val = Stack[LimLen][0];
                        if (val > S[rr]) -- LimLen; else break;
                    }
                }
            }
        int cl = min(NeedLen,LimLen);
        tmp = max(tmp,cl * 2 + MiLen);
        if (rr - rl + 1 == cl + MiLen) tmp = max(tmp,cl * 2 + MiLen + 2 * F[lr - cl][rl + cl + MiLen]);
    }
    return tmp;
}

int Calc()
{
    Get_F();
    //calc middle as a position
    int tmp = 0;
    for(int i = 1;i <= N;i ++)
    {
        int lr = i,rl = i,d = F[i][i];
        lr -= d,rl += d;
        tmp = max(tmp,TreatR(lr,-1,rl) + 2 * d - 1);
    }
    //calc middle as a middle
    for(int i = 1;i < N;i ++)
    {
        int lr = i,rl = i + 1,d = F[i][i + 1];
        lr -= d,rl += d;
        tmp = max(tmp,TreatR(lr,-1,rl) + 2 * d);
    }
    //calc those when the sorted make difference
    for(int i = 1;i <= N;i ++)
    {
        int cent = -1;
        for(int j = i + 1;j <= N;j ++)
            if (S[j] < S[i]) {cent = S[j];break;}
        tmp = max(tmp,TreatR(i,cent,i + 1));
    }
    return tmp;
}

void Work()
{
    static int Bak[MAXN];
    for(int i = 1;i <= N;i ++) scanf("%d", &S[i]);
    int ans = Calc();
    memcpy(Bak,S,sizeof Bak);
    for(int i = 1;i <= N;i ++) S[i] = C - S[i] + 1;
    reverse(S + 1,S + N + 1);
    ans = max(ans,Calc());
    memcpy(Bak,S,sizeof Bak);
    int c = 0,cr = 0;
    sort(S + 1,S + N + 1);
    for(int i = 1;i <= N;i ++)
        if (S[i] != S[i - 1]) ans = max(ans,cr),cr = 1; else ++ cr;
    ans = max(ans,cr);
    printf("%d
", ans);
}

int main()
{
    while (scanf("%d%d", &N, &C) != EOF) Work();
    return 0;
}