|
http://acm./showproblem.php?pid=4513 Problem Description 吉哥又想出了一個(gè)新的完美隊(duì)形游戲！假設(shè)有n個(gè)人按順序站在他的面前，他們的身高分別是h[1], h[2] ... h[n]，吉哥希望從中挑出一些人，讓這些人形成一個(gè)新的隊(duì)形，新的隊(duì)形若滿足以下三點(diǎn)要求，則就是新的完美隊(duì)形： 1、挑出的人保持原隊(duì)形的相對(duì)順序不變，且必須都是在原隊(duì)形中連續(xù)的； 2、左右對(duì)稱，假設(shè)有m個(gè)人形成新的隊(duì)形，則第1個(gè)人和第m個(gè)人身高相同，第2個(gè)人和第m-1個(gè)人身高相同，依此類推，當(dāng)然如果m是奇數(shù)，中間那個(gè)人可以任意； 3、從左到中間那個(gè)人，身高需保證不下降，如果用H表示新隊(duì)形的高度，則H[1] <= H[2] <= H[3] .... <= H[mid]。 現(xiàn)在吉哥想知道：最多能選出多少人組成新的完美隊(duì)形呢？ ? ? Input 輸入數(shù)據(jù)第一行包含一個(gè)整數(shù)T，表示總共有T組測(cè)試數(shù)據(jù)(T <= 20)；每組數(shù)據(jù)首先是一個(gè)整數(shù)n(1 <= n <= 100000)，表示原先隊(duì)形的人數(shù)，接下來(lái)一行輸入n個(gè)整數(shù)，表示原隊(duì)形從左到右站的人的身高（50 <= h <= 250，不排除特別矮小和高大的）。 ? ? Output 請(qǐng)輸出能組成完美隊(duì)形的最多人數(shù)，每組輸出占一行。 ?? Sample Input 2 3 51 52 51 4 51 52 52 51 ?? Sample Output 3 4 ?? Source 2013騰訊編程馬拉松初賽第二場(chǎng)（3月22日） ?? Recommend liuyiding 題意：求最長(zhǎng)遞減回文串#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[100009] , b[200009];
int p[200009];
int num;
int main()
{
int t ;
scanf("%d" , &t);
while(t--)
{
int l ;
scanf("%d" , &l);
for(int i = 0 ; i < l ; i )
{
scanf("%d" , &a[i]);
}
int len = 0 ;
b[len ] = -1;
b[len ] = -1 ;
for(int i = 0 ; i < l ; i )
{
b[len ] = a[i];
b[len ] = -1 ;
}
int mx = -1 , mid , ans = 0;
for(int i = 1 ; i < len ; i )
{
if(mx > i)
{
p[i] = min(p[2*mid-i] , mx - i);
}
else
{
p[i] = 1 ;
}
while(b[i-p[i]] == b[i p[i]] && b[i - p[i] 2] >= b[i - p[i]])//從中間往兩邊遞減
{
p[i] ;
}
if(mx < p[i] i)
{
mid = i ;
mx = p[i] i;
}
ans = max(ans , p[i] - 1);
}
printf("%d\n" ,ans);
}
return 0 ;
}
? 來(lái)源：https://www./content-4-376151.html |
|
|
來(lái)自： 印度阿三17 > 《開(kāi)發(fā)》
