CF5E Bindian Signalizing
Loner_Knowledge
2018-02-04 20:28:09
这是一道动态规划题
---
题意是有`n`座山组成一个环,两座山互相能看到的要求是相连的圆弧上没有任何其他的山高度比它们高,求能看到的山的组数。考虑一组山,我们让高度较小且的位置最靠左的那一座山负责贡献答案。
先把这个环变成一条链,把最高的山作为第一个山,按照顺序复制序列,再在最后接上一个最高的山。
设`left[i]`表示`i`左边第一个比`i`高的位置,`right[i]`表示`i`右边第一个比`i`高的位置,`count[i]`表示在`i`到`right[i]`的左开右闭区间内高度等于`i`的山的数目,那么每座山能看到的山的组数至少有`count[i]`组和`(i,l[i])`与`(i,r[i])`这两组,不过当`l[x]=0`且`r[x]=n`时其实是一组,注意判断。
于是问题就变成了求`left`数组、`right`数组和`count`数组,可以通过动态规划的思想来做。
注意**数据范围**,答案要用$long\ long$,$long\ long$在`CodeForces`要用`"%I64d"`输出。(当然如果你用`cout`另说)
```cpp
#include<cstdio>
int t[1000002],h[1000002],l[1000002],r[1000002],cnt[1000002];
int main() {
int n,p=0;
long long ans=0;
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%d",t+i);
for(int i=1;i<n;++i)
if(t[i]>t[p]) //寻找最大值
p=i;
for(int i=0;i<=n;++i)
h[i]=t[(i+p)%n]; //转环为链
for(int i=1;i<=n;++i) {
l[i]=i-1; //初始化为i左边第一个
while(l[i]&&h[i]>=h[l[i]])
l[i]=l[l[i]]; //满足条件便递推
}
for(int i=n-1;i>=0;--i) {
r[i]=i+1; //初始化为i右边第一个
while(r[i]<n&&h[i]>h[r[i]])
r[i]=r[r[i]]; //满足条件便递推
if(r[i]<n&&h[i]==h[r[i]]) {
cnt[i]=cnt[r[i]]+1; //递推count数组
r[i]=r[r[i]];
}
}
for(int i=0;i<n;++i) {
ans+=cnt[i]; //至少能看到的组数
if(h[i]<h[0]) {
ans+=2; //另外的两组
if(!l[i]&&r[i]==n)
ans--; //特判是同一组的情况
}
}
printf("%I64d\n",ans);
return 0;
}
```
---