单调栈 例题:POJ-3250,HDU-1506以及POJ-2796

  • Post author:
  • Post category:其他


蒟蒻的第一篇专题……

最近(两天)都在研究单调栈,一开始学单调栈是看这篇文章学的

传送门


ps:顺便吐槽一下单调队列那一题,用g++和stdio交会tle,用c++或者用iostream输出都能ac,估计是poj那个老旧的评测机的锅



概述

单调栈是用来干什么的呢?那篇博文讲得不错

单调是一种思想,当我们解决问题的时候发现有许多冗杂无用的状态时,我们可以采用单调思想,用单调队列或类似于单调队列的方法去除冗杂状态,保存我们想要的状态

单调栈和单调队列十分类似,都采用了单调思想来去除一些冗余状态,但我一开始没有搞懂单调栈在实际运用中所起到的作用



菜鸡的假算法(本人反思)

POJ-3250

拿POJ3250做例子,一开始我没有完全理解单调栈的时候做了一遍,并且AC了【证明这题题有点水,贴上错误示例

#include<cstdio>

long long h[100011],s[100011],val[100011],top = 0;
long long n,ans = 0;
int main()
{
    scanf("%lld",&n);
    for (int i = 0;i < n;++i)
    {
        scanf("%lld",h + i);
        while (h[i] >= h[s[top]] and top > 0) 
        {
            top--;
            val[top] += val[top + 1];
            ans += val[top + 1];
        }
        val[top]++;
        s[++top] = i;
        val[top] = 0;
    }
    while (top > 0) 
    {
        top--;
        val[top] += val[top + 1];
        ans += val[top + 1];
    }
    printf("%lld",ans);
    return 0;
}

当时我是这样想的……【翻草稿ing

建一个单调递减栈,开一个val数组记录每只牛能看到多少只牛,一个数在入栈之前将原本的栈顶记录的数+1(因为这个数比之前的栈顶小),在出栈时把自己记录的数给下一层(因为这层能看到的下一层必定能看到),这里就不放图了

这个假算法对于这一道题确实能过,然而下一题就不一样了……

HDU-1506


HDU-1506

这题我一开始是想dp的,但因为刚学单调栈,所以就尝试用单调栈做

但这题用回我的假算法做就不一样了,因为这题比上一题复杂了,错误示范不讲详细过程,最后我推出了一条”状态转移方程”

对于每一个栈:





a

n

s

=

m

a

x

(

s

t

a

c

k

[

i

]

(

i

d

[

t

o

p

]

i

d

[

i

1

]

)

)

ans=max(stack[i]·(id[top]-id[i-1]))






a


n


s




=








m


a


x


(


s


t


a


c


k


[


i


]







(


i


d


[


t


o


p


]













i


d


[


i













1


]


)


)






从1到top枚举i

好吧,我相信大佬们一眼就看出来这TLE了,然而可怜的我不太会算时间复杂度

这次错误代码也不贴了



真正的单调栈

经过了一个上午的折腾(期间我改了一下思路,写了个WA的程序,用上述TLE程序对拍,结果把WA程序改对之后也TLE了,也就是花了一个上午时间写了一个我写了10多分钟的程序),我终于发现单调栈除了单调性之外还有其它的特性,例如数列



{

93

,

10

,

40

,

85

,

47

,

19

,

56

}

\{93,10,40,85,47,19,56\}






{



9


3


,




1


0


,




4


0


,




8


5


,




4


7


,




1


9


,




5


6


}






模拟一次单调递减栈

先将93和10入栈

top=2 1 2 3 4 5
stack 93 10
id 1 2

将40入栈,发现此时栈顶元素比40小,将10出栈,再将40入栈

top=2 1 2 3 4 5
stack 93 40
id 1 3

将85入栈,同理先将40退栈,后面47,19可以直接入栈

top=4 1 2 3 4 5
stack 93 85 47 19
id 1 4 5 6

最后将56入栈,同理将top减到2再入栈

top=3 1 2 3 4 5
stack 93 85 56
id 1 4 7

这就是整个

从左到右

的入栈次序了,有一些比较聪明的人可能已经看出id之间的关系,像我这么蠢的人联系一下上面那条式子应该也能想到一些东西

因为出栈的都是比当前栈顶小的数,我们只需要比较一下

入栈前

的栈顶id和

准备进栈

的id,也就是



i

i

d

[

t

o

p

]

1

i – id[top] – 1






i













i


d


[


t


o


p


]













1





,就能轻松地得到在当前元素

左边

比其小的元素个数了

知道了这件事,我们只要从左到右扫一遍,再反过来扫一遍,就能知道每一个元素的左右两边一共有多少个比它大(小)的元素了

回到HDU-1506,我们要找到每一个元素左右两边有多少比它大的元素,这样才能以目前元素为高建立一个长方形

#include<cstdio>
#include<cstring>

long long stack[100011],id[100011],h[100011],ans1[100011],ans2[100011],top = 0;

int main()
{
    long long n,ans;
    while (~scanf("%lld",&n) and n != 0)
    {
        ans = 0,top = 0;
        memset(ans1,0,sizeof(ans1));
        memset(ans2,0,sizeof(ans2));
        id[0] = 0;
        for (int i = 1;i <= n;++i)
        {
            scanf("%lld",h + i);
            while (top > 0 and stack[top] >= h[i]) top--;
            ans1[i] = i - id[top];
            stack[++top] = h[i];
            id[top] = i;
        }
        top = 0;
        id[0] = n + 1;
        for (int i = n;i >= 1;--i)
        {
            while (top > 0 and stack[top] >= h[i]) top--;
            ans2[i] = id[top] - i;
            stack[++top] = h[i];
            id[top] = i;
        }
        for (int i = 1;i <= n;++i)
        {
            ans = max(ans,(ans1[i] + ans2[i] - 1) * h[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

代码在这了,记住用LL哦

再给出POJ-3250的正解(虽然上面那个也能AC)

#include<cstdio>

long long h[100011],s[100011],top = 0;

long long n,ans = 0;
int main()
{
    scanf("%lld",&n);
    for (int i = 0;i < n;++i)
    {
        scanf("%lld",h + i);
        while (top > 0 and h[i] >= s[top]) top--;
        ans += top;
        s[++top] = h[i];
    }
    printf("%lld",ans);
    return 0;
}


HDU-1506


POJ-3250



练习

在这里插入图片描述


POJ-2796 Feel Good


代码在下面(会折叠的大佬教我一下?)





\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad













WA的话……

试试全是0的话会输出什么←反正我被坑了





\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad











#include<cstdio>
#define max(a,b) (a > b ? a : b)
long long stack[100011],id[100011],top,l[100011],r[100011],a[100011],sum[100011];
long long ans,al = 1,ar = 1;
int main()
{
    int n;
    scanf("%d",&n);
    top = 0,id[0] = 0,ans = 0;
    for (int i = 1;i <= n;++i)
    {
        scanf("%lld",a + i);
        sum[i] = a[i] + sum[i - 1];
        while (top > 0 and a[i] <= stack[top]) --top;
        l[i] = id[top] + 1;
        stack[++top] = a[i];
        id[top] = i;
    }
    top = 0,id[0] = n + 1;
    for (int i = n;i >= 1;--i)
    {
        while (top > 0 and a[i] <= stack[top]) --top;
        r[i] = id[top] - 1;
        stack[++top] = a[i];
        id[top] = i;
    }
    for (int i = 1;i <= n;++i)
    {
        long long tot = a[i] * (sum[r[i]] - sum[l[i] - 1]);
        if (tot > ans)
        {
            ans = tot;
            al = l[i],ar = r[i];
        }
    }
    printf("%lld\n%lld %lld",ans,al,ar);
    return 0;
}



版权声明:本文为juseice原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。