题解 P2422 【良好的感觉】

玫葵之蝶 · 2017-07-06 09:51:41 · 题解

这题数据太水了

我看了这个题之后，本来打算投机取巧一下，写个70分的代码，结果就AC了。。。

我的思路：枚举每个点，并双向扩展大于等于它的点，这样就可以找到在它是最小点的情况下的最大区间了，然后计算，答案就是最大值。

时间复杂度：一般情况应该可以过，可是如果卡一个所有数字相同的情况，就退化成O(n²)了，显然过不了，可是居然过了，而且总时间才106ms，简直不可思议。

希望各位julao可以来我的博客看看：blog

下来贴代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
using namespace std;
int n;
int a[100001];
ll f[100001];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        f[i]=a[i];
        for(int j=i-1;j>=1;j--){
            if(a[j]>=a[i]){
                f[i]+=a[j];
            }
            else{
                break;
            }
        }
        for(int j=i+1;j<=n;j++){
            if(a[j]>=a[i]){
                f[i]+=a[j];
            }
            else{
                break;
            }
        }
        f[i]=f[i]*a[i];
        ans=max(ans,f[i]);
    }
    printf("%lld",ans);
    return 0;
}