Feel Good （poj 2796）-白红宇

Feel Good （poj 2796）

阅读量：5302 次

发布时间：2019-06-14

本文共 3538 字，大约阅读时间需要 11 分钟。

题目大意就是在给出的串中找出一段连续数字，使得这一段的和乘上这一段最小的数的结果最大。

可以用rmq做。每次区间找当中最小的数，算出值并记录位置。然后再递推它的左右区间。

不过- -，一开始用深搜递推RE了。栈空间不够了，然后慢慢优化，最后还是ac了。

貌似这一题是用单调栈做的，还可以用查并集做。。。我也是醉了

具体看代码吧

ps：单调栈的代码在第二段

1 /************************************************************************* 2     > File Name: c.cpp 3     > Author: milaso 4     > Mail: 562058113@qq.com  5     > Created Time: 2014年07月21日 星期一 21时18分40秒 6  ************************************************************************/ 7 //#pragma comment(linker, "/STACK:1024000000,1024000000") 8 //如果自己电脑上100000的数据过的了，但是oj RE 那就加上上面的代码 9 #include
     
      10 #include
      
       11 #include
       
        12 #include
        
         13 #include
         
          14 #include
          
           15 #include
           
            16 using namespace std;17 18 int num[100010];19 long long sum[100010];20 int pos[100010][17]; // 最好只开17吧，不然可能RE21 int n;22 23 struct node{24 long long ans;25 int l,r;26 };27 28 29 void rmq_ini(){30 for(int i=1;i<=n;i++) pos[i][0] =i;31 for(int j=1;(1<
            
             <=n;j++)32 for(int i=1;(i+(1<
             
              <= n;i++ ){33 if(num[pos[i][j-1]] < num [pos[i+(1<<(j-1))][j-1]]){34 pos[i][j] = pos[i][j-1];35 }36 else 37 pos[i][j] = pos[i+(1<<(j-1))][j-1];38 }39 }40 41 int rmq(int l,int r){42 int k=0;43 while((2<
              
               <=(r-l+1)) k++;44 if(num[pos[l][k]] < num[pos[r-(1<
               
                 an.ans){70 an.ans= a.ans;71 an.l=a.l;an.r=a.r;72 }73 a =dfs(m,r);74 if(a.ans > an.ans){75 an.ans =a.ans;76 an.l=a.l;an.r=a.r;77 }78 return an;79 }80 81 82 83 int main(){84 scanf("%d",&n);85 for(int i=1;i<=n;i++){86 scanf("%d",&num[i]);87 sum[i] = sum[i-1] + num[i];88 }89 rmq_ini();90 node ans=dfs(0,n);91 //long long ans=dfs(0,n);92 //cout<
                
                 <

单调栈：

在栈中的数据保持递增，如果栈顶元素现在元素大，那么出栈，并且计算值。

栈中的值是某个区间的最小值。还需要记录栈中这个元素的区间的和以及区间的左右。

例子：

3 1 6 4 5 2

3进入：

栈：3（l=1,r=1,sum=1）

1进入：

3出栈，计算3的值为9 1 进栈

栈：1(l=1,l=2,sum=4)

6进入：

栈：1(l=1,l=2,sum=4)，6(l=3,r=3,sum=6)

4进入：

6出栈计算6为36

栈：1（l =1, r=2,sum=4）， 4（l = 3, r=4,sum =10）

5进入：

栈：1（l =1, r=2,sum=4）， 4（l = 3, r=4,sum =10），5（l=5,r=5,sum=5）

2进入：

5先出计算5 为25，接着计算4，计算4的时候要加上5的sum（因为5的区间的最小值为5,比4大，所以要加5区间的和），计算出来为60

栈：1（l =1, r=2,sum=4），2（l=3,r=6,sum=17）

最后，要计算栈中还未计算的元素。

每个都出栈。2计算为34 1计算时要加上2的sum，理由同上，计算出来为21.

最后的答案为60.

具体细节看代码吧！

/*************************************************************************    > File Name: 2796.cpp    > Author: milaso    > Mail: 562058113@qq.com     > Created Time: 2014年07月22日 星期二 12时39分29秒 ************************************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int MAXN = 100010;struct node{ int l,r; long long sum; long long a;};node sta[MAXN];int main(){ int n; scanf("%d",&n); long long ans=-1;int top=0;int lastn=-1,ansl,ansr; for(int i=1;i<=n;i++){ int now; scanf("%d",&now); if(now>=lastn){ sta[top].sum = now; sta[top].l = i; sta[top].r = i; sta[top].a = now;top++; } else{ long long nsum=0;int tl; while(top){ if(now < sta[top-1].a){ nsum += sta[top-1].sum; if(nsum * sta[top-1].a > ans){ ans = nsum*sta[top-1].a; ansl=sta[top-1].l; ansr=i-1; } tl = sta[top-1].l; top -- ; } else break; } sta[top].sum = nsum + now; //sta[top].l = ; sta[top].r = i; sta[top].a = now;top++; } lastn = sta[top -1].a; } long long nsum=0; while(top){ nsum += sta[top-1].sum; if(nsum * sta[top-1].a > ans) { ans = nsum*sta[top-1].a; ansl=sta[top-1].l; ansr=n; }top--; } printf("%lld\n%d %d\n",ans,ansl,ansr); return 0;}