美文网首页DataStructure
POJ-2796(单调栈)

POJ-2796(单调栈)

作者: 雨落八千里 | 来源:发表于2019-06-10 19:44 被阅读0次

    单调栈的运用:

    一系列数中取一个子序列使得子序列和乘以子序列中的最小值使得这个值最大。

    思想:

    要保证自己是一段区间的最小值,如何保证自己是区间的最小值呢?
    找出比自己小的数,不加入区间,自己就不是最小的了.....
    从当前数向左遍历找出比自己小的第一个数的下标l,从当前的数向右遍历,找出比自己小的第一个数的下标r,那么区间[l+1,r-1]就可以保证当前的数是最小的啦!!!!

    Feel Good

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<stack>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int R[101000],L[101000];
    int a[101000];
    ll sum[101000];
    stack<int>s;
    int main( )
    {
          int n;
          scanf("%d",&n);
          for(int i=1;i<=n;i++)
          {
                scanf("%d",&a[i]);
                if(i==1)
                {
                      sum[1]=a[1];
                }
                else
                {
                      sum[i]=sum[i-1]+a[i];
                }
    
          }
          for(int i=1;i<=n;i++)
          {
                while(!s.empty( )&&a[s.top( )]>=a[i])//找出每个数向左遍历比自己小的第一个数
                {
                      s.pop( );
                }
                if(s.empty( ))
                {
                      L[i]=0;
                }
                else
                {
                      L[i]=s.top( );
                }
                s.push(i);
          }
          /*for(int i=1;i<=n;i++)
          {
                cout<<L[i]<<" ";
          }
          cout<<endl;*/
          while(!s.empty( ))
          {
                s.pop( );
          }
          for(int i=n;i>0;i--)
          {
                while(!s.empty( )&&a[s.top( )]>=a[i])//找出每个数向右遍历比自己小的第一个数
                {
                      s.pop( );
                }
                if(s.empty( ))
                {
                      R[i]=n+1;
                }
                else
                {
                      R[i]=s.top( );
                }
                s.push(i);
          }
          /*for(int i=1;i<=n;i++)
          {
                cout<<R[i]<<" ";
          }
          cout<<endl;*/
          ll ans=-1;
          int left=1;
          int right=1;
          for(int i=1;i<=n;i++)
          {
                if(ans<(sum[R[i]-1]-sum[L[i]])*a[i])
                {
                      ans=(sum[R[i]-1]-sum[L[i]])*a[i];
                      left=L[i]+1;
                      right=R[i]-1;
                }
          }
          printf("%lld\n",ans);
          printf("%d %d\n",left,right);
          return 0;
    }
    

    相关文章

      网友评论

        本文标题:POJ-2796(单调栈)

        本文链接:https://www.haomeiwen.com/subject/zeptfctx.html