2013腾讯马拉松初赛 ACM 吉哥系列故事——完美队形II

[c]代码库

/*

2013腾讯马拉松初赛第2场

1004 吉哥系列故事——完美队形II
 
Time Limit: 1.0 Seconds   Memory Limit: 65536K
 

吉哥又想出了一个新的完美队形游戏！
假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] ... h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形：

1、挑出的人保持原队形的相对顺序不变，且必须都是在原队形中连续的；
2、左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然如果m是奇数，中间那个人可以任意；
3、从左到中间那个人，身高需保证不下降，如果用H表示新队形的高度，则H[1] <= H[2] <=  H[3] .... <= H[mid]。

现在吉哥想知道：最多能选出多少人组成新的完美队形呢？ 

Input

输入数据第一行包含一个整数T，表示总共有T组测试数据(T <= 20)；
每组数据首先是一个整数n(1 <= n <= 100000)，表示原先队形的人数，接下来一行输入n个整数，表示原队形从左到右站的人的身高（50 <= h <= 250，不排除特别矮小和高大的）。

Output

请输出能组成完美队形的最多人数，每组输出占一行。

Sample Input

2
3
1 2 1
4
1 2 2 1

Sample Output

3
4

*/


/*
解题报告：

这题其实是求一个最长的回文子串，这儿和以前不一样的是要求是先上升后下降。
我们可以通过Manacher算法改造过来
*/

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
typedef __int64 lld;

const int MAX = 110000 * 2;
int str[MAX];//原字符串
int sb[MAX];
int p[MAX];//表示以i为中心的回文半径，
/*p[i]-1刚好是原字符串以第i个为中心的回文串长度。
画画图就知道了，因为两端配匹的肯定是字符g
*/
/*
Mancher主算法

功能：求出以i为中心的回文半径p[i];
参数：传入构造好的字符串长度
特殊说明：因为前面加了一个无效字符，所以下标从1开始。
*/
bool dig(char x) {
    return x >= '0' && x <= '9';
}
int getval() {
    int ret = 0, sign = 1;
    char c;
    while(!dig(c = getchar()) && c != '-');
    if(c == '-')sign = -1;
    else ret = c - '0';
    while(dig(c = getchar()))ret = ret * 10 + c - '0';
    return ret * sign;
}
void Manacher(int n) {
    int i;
    int mx = 0; //记录前面回文串最长影响到的地方。不一定是最长回文串造成的。
    int id;//最长影响串的ID;
    p[0] = 0;
    for(i = 1; i < n; i++) {
        p[i] = 1; //至少是1
        if(mx > i) { //i受到影响即，id+p[id]-1>=i;
            p[i] = p[2 * id - i]; //2*id-i是i关于id的对称点相当于是id-(i-id);
            if(mx - i < p[i])p[i] = mx - i;
            //由于对称点的回文半径可能超过mx-i,因为mx后面的还没有配过
            //所以要取小的。等等继续配
        }

        //向两端配匹
        while(str[i - p[i]] == str[i + p[i]]) {
            if(str[i + p[i]] == 1) {
                p[i]++;
            } else {
                int a = i - p[i];
                int b = i + p[i];

                if(a + 2 <= b - 2 && str[a] <= str[a + 2] && str[b - 2] >= str[b]) {
                    p[i]++;
                    continue;
                } else if(a == b) {
                    p[i]++;
                    continue;
                } else if(a + 2 > b - 2) {
                    p[i]++;
                    continue;
                }


                break;
            }
        }

        if(i + p[i] > mx) {
            mx = i + p[i];
            id = i;
        }
    }
}

/*
功能：构造字符串，在每一个字符前插入一个，g,一般用'#'
第一个字符前面再插入,first,一般用'$'
最后再插入g字符
总之不是在输入中出现的字符就行了。
比如abb,构造成$#a#b#b#
参数：<first,第一个字符>，<g,一般字符>

返回值：构造好的字符串长度
*/
int pre(int first, int g, int m) {
    int i, n = 0;
    memcpy(sb, str, sizeof(int) * (m + 2));
    str[0] = first;
    n++;
    for(i = 0; i < m; i++) {
        str[n++] = g;
        str[n++] = sb[i];
    }

    str[n++] = g;
    str[n] = 3;
    return n;
}
int main() {
    int n;
    int i;
    int CS = 1;
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            //scanf("%d",&str[i]);
            str[i] = getval();
        }
        n = pre(0, 1, n);
        Manacher(n);
        int ans = 0;

        for(i = 1; i < n; i++) {
            if(p[i] > ans)ans = p[i];
        }

        printf("%d\n", ans - 1);
    }
    return 0;
}