HDOJ 4512 - 吉哥系列故事——完美队形I

     简单的dp...枚举中间点...先处理中间点是一个还是两个..用dp [ i ]代表这个回文在后半段某个位置的最大长度...

Program:

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#define ll long long
#define oo 1000000000
using namespace std;
int h[205],n,dp[205],ans;
int main()
{
int T,i,j,k,m;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&h[i]);
ans=0;
for (i=1;i<=n;i++) //枚举中简点
{
memset(dp,0,sizeof(dp));
dp[i]=1;
for (j=i+1;j<=n;j++)
if (h[i]==h[j]) break;
if (j<=n) dp[j]=2; // 是否可以两个中间点
for (k=i-1;k>=1;k--)
{
m=0;
for (j=i;j<=n;j++)
{
if (h[j]>h[k] && dp[j]>m) m=dp[j];
if (h[j]==h[k]) dp[j]=m+2;
}
}
for (j=i;j<=n;j++)
if (ans<dp[j]) ans=dp[j];
}
printf("%d\n",ans);
}
return 0;
}