Codeforces5E - Bindian Signalizing

题意：有N座山组成一个环，两座山互相能看到的要求是相连的圆弧上没有任何其他的山高度比它们高。求能看到的山的组数。

先把这个环变成一个链，即把最高的山作为第一个山，然后求出每一座山左边和右边第一个高于本身的位置，并且求出本位置到右边第一个高于本身的位置中一样高度的山。

用一种动态规划的想法大约线性多一点的时间求出left和right还有c数组。然后每一个座山只要左，右边有比他高的，那么就是两种，要么就只有一种

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Max(a,b) a>b?a:b
const int maxn=1000005;
int a[maxn],b[maxn],lef[maxn],rig[maxn],c[maxn]={0};
int main()
{
int n;
scanf("%d",&n);
int ma=-1,mid=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]>ma)
{
ma=a[i];
mid=i;
}
}
mid--;
for(int j=1;j<=n;j++)
b[j]=a[(mid+j)%n];
lef[1]=1;
for(int i=2;i<=n;i++)
{
lef[i]=i-1;
while(lef[i]>1&&b[lef[i]]<=b[i])
lef[i]=lef[lef[i]];//往左递归
}
for(int i=n;i>=1;i--)
{
rig[i]=i+1;
while(rig[i]<=n&&b[rig[i]]<b[i])
rig[i]=rig[rig[i]];//往右递归
if(rig[i]<=n&&b[rig[i]]==b[i])
{
c[i]=c[rig[i]]+1;
rig[i]=rig[rig[i]];
}
}
long long ans=0;
for(int i=2;i<=n;i++)
{
ans+=c[i]+2;
if(lef[i]==1&&rig[i]==n+1)
ans--;
}
printf("%lldn",ans);
}

最后

以上就是聪慧钢铁侠为你收集整理的Codeforces5E - Bindian Signalizing的全部内容，希望文章能够帮你解决Codeforces5E - Bindian Signalizing所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。