HDU 5371 Hotaru's problem（Manacher算法+贪心）

manacher算法详见

http://blog.csdn.net/u014664226/article/details/47428293

题意：给一个序列，让求其最大子序列，这个子序列由三段组成，第一段和第二段对称,第一段和第三段一样。

思路：首先利用Manacher算法求出以随意两个相邻元素为中心的回文串长度，用a[i]表示i-1,i为中心的回文串长度的一半，

那么问题就转化成了求最大的x，使得a[i]>=x,a[i+x]>=x,这一步能够贪心来做。

将a[i]从大到小排序（间接排序保留下标），设a[i]在原序列的下标为j，

每次将j放入set中，然后二分找到下标大于等于j-a[i]的最小值和下标小于等于j+a[i]的最大值，

这样能够就求出ans

</pre><pre class="cpp" name="code">#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<map>

#include<set>

#define eps 1e-6

#define LL long long

#define pii (pair<int, int>)

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const int maxn = 2*100000+1000;

const int INF = 0x3f3f3f3f;

int s[maxn];

int p[maxn], n, a[maxn], r[maxn];

bool cmp(int t1, int t2) {

    return a[t1] > a[t2];

}

set<int> Set;

struct Manacher {

    void solve() {

        int len=n,id=0,maxlen=0;

        for(int i=len;i>=0;--i){//插入'#'

            s[i+i+2]=s[i];

            s[i+i+1]=-1;

        }

        s[0]=-2;

        for(int i=2;i<2*len+1;++i){

            if(p[id]+id>i)p[i]=min(p[2*id-i],p[id]+id-i);

            else p[i]=1;

            while(s[i-p[i]] == s[i+p[i]])++p[i];

            if(id+p[id]<i+p[i])id=i;

            if(maxlen<p[i])maxlen=p[i];

        }

    }

} manacher;

int main() {

    //freopen("input.txt", "r", stdin);

    int T; cin >> T;

    int kase = 0;

    while(T--) {

        scanf("%d", &n);

        for(int i = 0; i < n; i++) scanf("%d", &s[i]);

        s[n] = -3;

        manacher.solve();

        int cnt = 0;

        for(int i = 3; i <= 2*n; i += 2) {

            a[++cnt] = (p[i]-1)/2;

            r[cnt] = cnt;

        }

        //for(int i = 1; i <= cnt; i++) cout << a[i] << endl;

        sort(r+1, r+cnt+1, cmp);

        Set.clear(); int ans = 0;

        for(int i = 1; i <= cnt; i++) {

            Set.insert(r[i]);

            set<int>::iterator t1 = Set.lower_bound(r[i]-a[r[i]]);

            set<int>::iterator t2 = --Set.upper_bound(r[i]+a[r[i]]);

            ans = max(ans, max(r[i]-*t1, *t2-r[i]));

        }

        ans *= 3;

        printf("Case #%d: %d\n", ++kase, ans);

    }

    return 0;

}