DESCRIPTION:
一个长度为n 的序列，对于每个位置i 的数ai 都有一个优美值，其定义是：找到序列中最
长的一段[l, r]，满足l<i<r，且[l, r] 中位数为ai（我们比较序列中两个位置的数的大小时，
以数值为第一关键字，下标为第二关键字比较。这样的话[l, r] 的长度只有可能是奇数），r - l
+ 1 就是i 的优美值。
接下来有Q 个询问，每个询问[l, r] 表示查询区间[l, r] 内优美值的最大值。
INPUT:
第一行输入n 接下来n 个整数，代表ai 接下来Q，代表有Q 个区间接下来Q 行，每行
两个整数 l, r 表示区间的左右端点
OUTPUT:
对于每个区间的询问，输出答案
SAMPLE INPUT:
8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8
SAMPLE OUTPUT:
7
3
1
3
5
3
7
3
数据范围：
30%: N,Q<50
70%:N,Q<2000
100%:N<2000,Q<100000,ai<200
对于所有数据，满足n 2000, Q <100000,ai <200
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int main() { freopen("beautiful.in","r",stdin); freopen("beautiful.out","w",stdout); static int a[2001],b[8001],v[2001],f[2001][2001]; int *l(b+2000),*r(b+6000); int n(0),cnt(0); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); for(int i=1;i<=n;i++) { cnt=0; memset(b,0,sizeof(b)); l[0]=r[0]=i; for(int j=i-1;j>0;j--) { if(a[j]>a[i])cnt++; else cnt--; l[cnt]=j; } cnt=0; for(int j=i+1;j<=n;j++) { if(a[j]>=a[i])cnt++; else cnt--; r[cnt]=j; } v[i]=0; for(int j=-n;j<=n;j++) if(l[j]&&r[-j]) v[i]=max(v[i],r[-j]-l[j]+1); } for(int i=1;i<=n;i++) f[i][i]=v[i]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) f[i][j]=max(f[i][j-1],f[j][j]); int q(0); scanf("%d",&q); while(q) { q--; int lt(0),rt(0); scanf("%d%d",<,&rt); printf("%d\n",f[lt][rt]); } return 0; }
原文：http://www.cnblogs.com/JebediahKerman/p/6011310.html