【P2422】良好的感觉（单调栈优化DP//奇怪的暴力）

话说正解是单调栈优化DP，然而貌似根据某种玄学的推算，这个题暴力出解貌似也是可以的。首先，我们枚举所有的点作为最小点，然后横向展开，遇到更小的就停止。。。然后再操作一下，看上去时间O（N^2），然而由于数据的随机生成性，差不多能做到O（NlogN）出解，然而由于数据的过于随机性，这么做比正解还要快。。。但是如果数据整齐的话应该怎么办呢，比如都是同一个数的情况。。

这时我们可以先排序，从最大的开始搜起，然后如果有进行最优性剪枝，复杂度貌似可以保证在O（NlogN^2）左右。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define re register

#define wc 0.0000000001

using namespace std;

struct point

{

    int v,id;

};

point a[];

long long n,d[],ans,maxx,lt,sum;

inline bool cmp(point x,point y)

{

    return x.v>y.v;

}

int main()

{

    cin>>n;

    for(re int i=;i<=n;i++)

    {

        cin>>d[i];

        a[i].v=d[i];

        a[i].id=i;

        sum+=d[i];

    }

    sort(a+,a+n+,cmp);

    for(re int i=;i<=n;i++)

    {

        if(a[i].v*sum<=ans)

        continue;

        int l=a[i].id,r=a[i].id;

        long long cnt=a[i].v;

        while(d[l-]>=a[i].v)

        {

            cnt+=d[l];

            l--;

        }

        while(d[r+]>=a[i].v)

        {

            cnt+=d[r];

            r++;

        }

        maxx=a[i].v*cnt;

        ans=max(maxx,ans);

    }

    cout<<ans;

}

巴特西

【P2422】良好的感觉（单调栈优化DP//奇怪的暴力）

最新文章

热门文章