POJ 3250 Bad Hair Day(单调栈)

题目地址: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]; stackq; 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()]

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:Hdu 5029 Relief grain(树链剖分)
下一篇:Codeforces Round #268 (Div. 1)A(构造)
相关文章

POJ3621最优比率生成环 01分数规划问题

poj 1928

poj 3728 tarjan+带权路径并查集

poj 3321

POJ 1664 放苹果 递推

poj 1631

poj模拟题总结(一)

POJ 1083

POJ 1952 BUY LOW, BUY LOWER

poj 1195

图文推荐
POJ 3250 Bad Hair Day(单调栈)
ZOJ 3640 Help Me
POJ 3250 Bad Hair Day(单调栈)
CF 518C(Anya and
POJ 3250 Bad Hair Day(单调栈)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-07 人气:5
本文关键词:
分享到:

相关文章

  • POJ 3250 Bad Hair Day 2013-08-26

    顺手写个单调队列。。。。 Bad Hair Day Time Limit: 2000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u [Submit] [Go Back] [Status] Description Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious ab

  • SWERC 2011 / HDU 4196 Remoteland (数论&想法题) 2013-01-16

    Remoteland Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others) http://acm.hdu.edu.cn/showproblem.php?pid=4196 思路: 显然取n!是最大的,但这不一定是一个完全平方数,需要把多余的部分除掉。 可以利用勒让德定理很快处理出n!所有素因子的指数,偶数保留,奇数减1,即可保证这些素因子最后乘积为完全平方数,也就是用n!除以所有指数为

  • POJ 2482--Stars in Your Window(线段树+扫描线,二维区域最值转化为线段树-经典)最浪漫的题目 2013-03-29

    Stars in Your Window Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10044 Accepted: 2789 Description Fleeting time does not blur my memory of you. Can it really be 4 years since I first saw you? I still remember, vividly, on the beautiful

  • poj 2796 Feel Good (单调栈) 2013-06-02

    Feel Good Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 9778 Accepted: 2652 Case Time Limit: 1000MS Special Judge Description Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to stu

  • poj 2796 Feel Good(单调队列) 2014-06-22

    Feel Good Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 8598 Accepted: 2324 Case Time Limit: 1000MS Special Judge Description Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to stu

  • HDU 1535 && POJ 1511 Invitation Cards (SPFA 模板 + 反向建图) 2012-01-31

    Invitation Cards HDU: Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) POJ: Time Limit: 8000 MS Memory Limit: 262144 K Problem Description In the age of television, not many people attend theater performances. Antique

  • POJ 3225--Help with Intervals(线段树,成段替换+区间异或+hash) 2012-03-11

    Help with Intervals Time Limit: 6000MS Memory Limit: 131072K Total Submissions: 10444 Accepted: 2551 Case Time Limit: 2000MS Description LogLoader, Inc. is a company specialized in providing products for analyzing logs. While Ikki is working on gradu

  • HDU - 4028 The time of a day(离散+DP) 2012-04-20

    Description There are no days and nights on byte island, so the residents here can hardly determine the length of a single day. Fortunately, they have invented a clock with several pointers. They have N pointers which can move round the clock. Every

  • POJ 1087 A Plug for UNIX 会议室插座问题 构图+最大流 2012-05-01

    题目链接:POJ 1087 A Plug for UNIX A Plug for UNIX Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 13809 Accepted: 4623 Description You are in charge of setting up the press room for the inaugural meeting of the United Nations Internet eXecutiv

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.091 (s). 10 q(s)