POJ 3250 Bad Hair Day(单调栈) - c++编程基础

题目地址：POJ 3250

初学单调栈。多校和网络赛已经碰到两次了。

单调栈的原理简单的不能再简单了。。就是让栈里的元素从栈顶到栈底呈单调性。

比如说递增单调栈。

每次放进一个数的时候，如果栈顶的数小于要放的数，就把栈顶的数pop出来使得栈里保持单调性。

对于这道题来说，就从右往左开始遍历，建一个递增单调栈。那么每次pop出来的就是当前的牛可以看到的牛数。然后累加即可。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               using namespace std; #define LL long long LL a[100000], dp[100000]; stack
              
               q; int main() { int n, i, j; LL sum=0; scanf("%d",&n); for(i=0;i
               
                =0;i--) { dp[i]=1; while(!q.empty()&&a[q.top()]