首页 > 代码库 > POJ 3250 Bad Hair Day(单调栈)
POJ 3250 Bad Hair Day(单调栈)
题目地址:POJ 3250
初学单调栈。多校和网络赛已经碰到两次了。
单调栈的原理简单的不能再简单了。。就是让栈里的元素从栈顶到栈底呈单调性。
比如说递增单调栈。
每次放进一个数的时候,如果栈顶的数小于要放的数,就把栈顶的数pop出来使得栈里保持单调性。
对于这道题来说,就从右往左开始遍历,建一个递增单调栈。那么每次pop出来的就是当前的牛可以看到的牛数。然后累加即可。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> #include <stack> using namespace std; #define LL long long LL a[100000], dp[100000]; stack<int>q; int main() { int n, i, j; LL sum=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%lld",&a[i]); } memset(dp,0,sizeof(dp)); for(i=n-1;i>=0;i--) { dp[i]=1; while(!q.empty()&&a[q.top()]<a[i]) { dp[i]+=dp[q.top()]; sum+=dp[q.top()]; q.pop(); } q.push(i); } /*for(i=0;i<n;i++) { printf("%d ",dp[i]); }*/ printf("%lld\n",sum); return 0; }
POJ 3250 Bad Hair Day(单调栈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。