HDU 4513 길 고 시리즈 이야기 - 완벽 한 대형 II [Manacher]

Problem Description
길 형 은 또 새로운 완벽 한 대형 게임 을 생각해 냈 다!만약 에 n 명 이 순서대로 그의 앞 에 서 있다 고 가정 하면 그들의 키 는 h [1], h [2]... h [n] 이다. 길 고 는 그 중에서 몇 사람 을 골 라 서 이 사람들 로 하여 금 새로운 대형 을 형성 하 게 하고 자 한다. 새로운 대형 이 다음 과 같은 세 가지 요 구 를 만족 시 키 면 새로운 완벽 한 대형 이다.
1. 고 른 사람 은 원래 의 대형 을 유지 하 는 상대 적 인 순서 가 변 하지 않 고 모두 원래 의 대형 에서 연속 되 어야 한다.2. 좌우 대칭, m 개인 이 새로운 대형 을 형성한다 고 가정 하면 첫 번 째 사람 은 m 개인 과 키 가 같 고 두 번 째 사람 은 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
51 52 51
4
51 52 52 51

Sample Output

3
4

Source
2013 텐 센트 프로 그래 밍 마라톤 1 차 전 2 차 전 (3 월 22 일)
질문 링크: HDU 4513 길 고 시리즈 - 완벽 한 대형 II
문제 풀이 방향: Manacher 알고리즘 을 약간 수정 하여 정확 한 순 서 를 확보 하고 구체 적 으로 절 차 를 봅 니 다.
 
AC 의 C + + 프로그램:

#include
#include
#include

using namespace std;

const int N=200010;
int s[N],p[N],n;

int Manacher(int s[])
{
	p[0]=0;
	s[0]=-111; 
	for(int i=n;i>0;i--)
	  s[2*i]=s[i];
	n=2*n+1;
	for(int i=1;i<=n;i+=2)
	  s[i]=300;
	s[n+1]=111;
	int id=0,mx=0;
	for(int i=1;i<=n;i++)
	{
		p[i]=imx)
		{
			id=i;
			mx=i+p[i];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	  ans=max(ans,p[i]-1);
	return ans;
} 

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		  scanf("%d",&s[i]);
		int ans=Manacher(s);
		printf("%d
",ans);
	}
	return 0;
}