CF5E Bindian Signalizing

· · 题解

这是一道动态规划题

题意是有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另说）

#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;
}