首页 > 代码库 > BEAUTIFUL
BEAUTIFUL
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; }
BEAUTIFUL
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。