HDU 4513 哥几个系列故事——形成完善II manacher求最长回文

意甲冠军：中国

思维：在manacher断保证非严格递减即可了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100110;
int a[maxn<<1];
int b[maxn<<1];
int dp[maxn<<1];
int manacher(int n)
{
	int maxlen = 0, id, ans = 0;
	for(int i = 1; i < n; i++)
	{
		if(maxlen > i)
			dp[i] = min(dp[id*2-i], maxlen-i);
		else
			dp[i] = 1;
		int flag = 0, x = 1;
		if(a[i] != 1)
		{
			flag = 1;
			x = a[i];
		}
		while(a[i+dp[i]] == a[i-dp[i]])
		{
			if(a[i+dp[i]] == 1)
				dp[i]++;
			else
			{
				if(!flag)
				{
					x = a[i+dp[i]];
					dp[i]++;
					flag = 1;
				}
				else
				{
					if(a[i+dp[i]] > x)
						break;
					x = a[i+dp[i]];
					dp[i]++;
				}
			}
		}
		if(dp[i]+i > maxlen)
		{
			id = i;
			maxlen = dp[i]+i;
		}
		if(ans < dp[i])
			ans = dp[i];
	}
	return ans-1;
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n;
		scanf("%d", &n);
		a[0] = -1;
		a[1] = 1;
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i<<1]);
			a[i<<1|1] = 1;
		}
		n = n*2+2;
		a[n] = 2;
		printf("%d
", manacher(n));
	}
	return 0;
}