NYOJ-258/POJ-2559/HDU-1506 Largest Rectangle in a Histogram,最大长方形，dp或者单调队列！

这么经典的题硬是等今天碰到了原题现场懵逼两小时才会去补题。。。废话不多说：

题意：截取一个矩形使其面积最大，随你怎么截，反正面积要最大。输出最大面积，注意爆int。

思路：dp或单调队列。核心思路是从一个小矩形往两边扩散，分别找两边第一个小于这个矩形的位置，其中面积就是这个小矩形与区间长度的乘积，我们预处理出所有的小矩形的这两个端点值，然后扫一遍即可更新到最大值。

先看DP怎么做：其实我的理解dp是一种思想，类似dp。我们用l[i],r[i]来表示上述的两个值，然后初始都赋为i。我们更新时只需沿着上一个一直往前找，直到一个数不大于当前的数即可，然后将这个l[i]、r[i]用上一个来更新。

ll a[N],l[N],r[N];

int main()

{

    int n;

    while(~scanf("%d",&n)&&n)

    {

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

        {

            scanf("%I64d",&a[i]);

            l[i]=r[i]=i;

        }

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

        {

            while(l[i]>1&&a[l[i]-1]>=a[i])

                l[i]=l[l[i]-1];

        }

        for(int i=n;i>=1;i--)

        {

            while(r[i]<n&&a[r[i]+1]>=a[i])

                r[i]=r[r[i]+1];

        }

        ll ans=0;

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

            ans=max(ans,a[i]*(r[i]-l[i]+1));

        printf("%I64d\n",ans);

    }

    return 0;

}

单调栈：

说白了也是一种思想，每次对栈顶元素进行操作，如果维护的单增栈，则判断当前元素与栈顶元素，如果大于栈顶元素肯定直接入栈，否者重复出栈操作直到栈顶元素小于当前元素。单减栈同理，是不是很土。重要的还是思想，这种求第一个不大于a或不小于a[i]的位置就很好做了。

ll a[N],l[N],r[N];

int main()

{

    int n;

    while(~scanf("%d",&n)&&n)

    {

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

        {

            scanf("%lld",&a[i]);

            l[i]=r[i]=i;

        }

        stack<ll>q;

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

        {

            while(!q.empty()&&a[i]<=a[q.top()])

            {

                l[i]=l[q.top()];

                q.pop();

            }

            q.push(i);

        }

        while(!q.empty()) q.pop();

        for(int i=n; i>=1; i--)

        {

            while(!q.empty()&&a[i]<=a[q.top()])

            {

                r[i]=r[q.top()];

                q.pop();

            }

            q.push(i);

        }

        ll ans=0;

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

        {

            ans=max(ans,a[i]*(r[i]-l[i]+1));

        }

        printf("%lld\n",ans);

    }

    return 0;

}

思想很重要，学不能致用废矣！

巴特西

NYOJ-258/POJ-2559/HDU-1506 Largest Rectangle in a Histogram,最大长方形，dp或者单调队列！

最新文章

热门文章