【manacher】HDU4513-吉哥系列故事—

【manacher】HDU4513-吉哥系列故事——完美队形II

【题目大意】

求最长回文队伍且队伍由中间向两边递减。

【思路】

和字符串一样的做法，在递推的时候增加判断条件：a[i-p[i]]<=a[i-p[i]+2]。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 using namespace std;
 7 const int MAXN=100000+50;
 8 int a[MAXN*2];
 9 int p[MAXN*2]; 
10 int n;
11 
12 void init()
13 {
14     memset(a,0,sizeof(0));
15     scanf("%d",&n);
16     a[0]=-1;
17     a[1]=0;
18     for (int i=1,j=1;i<=n;i++)
19     {
20         scanf("%d",&a[++j]);
21         a[++j]=0;
22     }
23     n=n*2+1;
24 }
25 
26 void solve()
27 {
28     int mx=0,mxid=0;
29     memset(p,0,sizeof(p));
30     for (int i=1;i<=n;i++)
31     {
32         if (mx>i) p[i]=((p[2*mxid-i]<(mx-i))?p[2*mxid-i]:(mx-i));
33             else p[i]=1;
34         while (a[i-p[i]]==a[i+p[i]] && a[i-p[i]]<=a[i-p[i]+2]) p[i]++;
35         if (i+p[i]>mx)
36         {
37             mx=i+p[i];
38             mxid=i;
39         }
40     }
41 }
42 
43 int printans()
44 {
45     int ans=-1;
46     for (int i=1;i<=n;i++) ans=max(ans,p[i]);
47     ans--;
48     return ans;
49 }
50 
51 int main()
52 {
53     int T;
54     scanf("%d",&T);
55     for (int i=0;i<T;i++)
56     {
57         init();
58         solve();
59         cout<<printans()<<endl;
60     }
61     return 0;
62 }