HDU - 4513 吉哥系列故事——完美队形II（manacher算法变形）

题目链接

题意：

在一个序列中，找出最长的回文序列，并且满足从序列最左端到中间非递减，然后输出序列长度

思路：直接套用manacher模板，用0代替‘￥’ ，1代替‘#’进行预处理。 然后在p[i]数组向两边延申的时候判断一下 ，如果这个位置不是1 ，并且大于该位置的前两格，就说明此时不满足非递减要求，就break，中断延申过程。

#include<iostream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm> 
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include<sstream>
#include<time.h>
#define pi acos(-1)
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1e5+10;
int a[maxn];
int n;
int p[maxn*2];
int manacher()
{
    int mmax=-1;
    memset(p,0,sizeof(p));
    int len1=n;
    vector<int> s{0,1};
    for(int i=0;i<len1;i++) 
    {
        s.push_back(a[i]);
        s.push_back(1);
    }
    s.push_back(-1);//末尾插个-1，保证与0匹配失效
    int len2=s.size()-1;
    int mx=0,id=0;
    for(int i=1;i<=len2;i++)
    {
        if(i<mx) p[i]=min(mx-i,p[2*id-i]);
        else p[i]=1;
        while(s[p[i]+i]==s[i-p[i]])
        {
            if(s[p[i]+i]!=1 && s[i+p[i]-2]<s[i+p[i]]) break;//不满足递增回文串，就break
            p[i]++;
        }
        if(p[i]+i>mx)
        {
            mx=p[i]+i;
            id=i;
        }
        mmax=max(mmax,p[i]);
    }
    return mmax-1;
}
int main(){
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++) scanf("%d",a+i);
        cout<<manacher()<<'\n';
    }
    system("pause");
    return 0;
}

 /*　　　　　　　　┏┓　　 　┏┓
 * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　　　┃　　　　　　　┃ 　
 * 　　　　　　　┃　　　━　　 　┃
 * 　　　　　　　┃　＞　　　＜　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃...　⌒　... 　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┗━┓　　　┏━┛
 * 　　　　　　　　　┃　　　┃　      With the magic animal,Code will be far away from bug.　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃   
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃  　　　　　　
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┗━━━┓
 * 　　　　　　　　　┃　　　　　　　┣┓
 * 　　　　　　　　　┃　　　　　　　┏┛
 * 　　　　　　　　　┗┓┓┏━┳┓┏┛
 * 　　　　　　　　　　┃┫┫　┃┫┫
 * 　　　　　　　　　　┗┻┛　┗┻┛
 */