귀여운 단조 로 운 스 택: poj 2796, poj 2559,

성질:
1. 단조 로 운 스 택 이 증가 하면 스 택 꼭대기 에서 스 택 바닥 까지 의 요 소 는 엄 격 히 증가 합 니 다.단 조 롭 게 스 택 을 줄 이면 스 택 꼭대기 에서 스 택 바닥 까지 의 요 소 는 엄 격 히 줄어든다.
2. 창고 꼭대기 에 있 는 원소 에 가 까 울 수록 창고 에 들 어 갑 니 다.(창고 의 기본 성질)
동작:
창고 처럼 단조 로 운 창고 처럼 창고 에 들 어 가 는 것 과 출고 하 는 것.
스 택 에 들 어가 기 전에 스 택 에 들 어 가 는 요 소 를 검사 합 니 다:
예 를 들 어 4, 5, 3, 7, 7, 9.
                                                           9
    ->  5  ->    ->      ->  7   ->     -> 7 ->  7
 4      4      4      3        3       3      3      3
(1)    (2)    (3)    (4)      (5)     (6)    (7)    (8)
(1) 스 택 이 비어 있 고 4 스 택 에 들 어 갑 니 다.
(2) 4 < 5 설립, 5 입고
(3) 5 < 3 이 성립 되 지 않 고 5 가 창고 에서 나온다.
    (3) 4 < 3 은 성립 되 지 않 고 4 는 창고 에 들어간다.
(4) 스 택 이 비어 있 고 3 스 택 에 들 어 갑 니 다.
(5) 3 < 7 설립, 7 (first) 입고
(6) 7 (first) < 7 (second) 미 성립, 7 (first) 출고
(7) 3 < 7 (second) 설립, 7 (second) 입고
(8) 7 < 9 설립, 9 입고
응용: 성질 에 따라 1,
구간 최대 (최소) 값 구하 기:
매번 창고 에 들 어 갈 때마다 엄격하게 증가한다.
스 택 에 들 어가 지 못 했 습 니 다. 상단 요소 가 팝 업 되 었 습 니 다. 유지 구간 (즉, 스 택 에 스 택 지붕 을 더 한 구간 은 그 보다 크기 때문에 스 택 에 있 는 요 소 는 유지 후 구간 의 최소 값 입 니 다. 마찬가지 로 스 택 에 들 어 갈 요소 도 이 구간 을 더 해 야 합 니 다)
그래서 매번 창고 에 들 어 갈 때마다 구간 을 유지 하면 구간 의 최고 치 를 구 할 수 있다.
마지막 으로 남 은 원소 도 한 무더기 구간 이다.
그래서 시간 복잡 도 는 O (n) 에서 O (2n) 이다.
poj 2796 Feel Good
이 문 제 는 구간 을 유지 할 때 최대 치 를 구 하 는 것 이다.
구덩이  int  m 결국 터 졌 다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
const int maxn = (int)1e6+5;

LL sum[maxn]={0};

struct node
{
    int l,r,n;
}stk[maxn];
int tp;

node mn(int a,int b,int c)
{
    node t;
    t.n=a;
    t.l=b;
    t.r=c;
    return t;
}

LL calc(node a)
{
    //printf("%lld
",(sum[a.r]-sum[a.l-1])*(LL)a.n);
    return (sum[a.r]-sum[a.l-1])*(LL)a.n;
}

LL an=0,f;
int al,ar;
inline void ck(node a)
{
    LL m=calc(a);
    if(an<=m)
    {
        an=m;
        al=a.l;
        ar=a.r;
    }
}

int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out1","w",stdout);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        an=0;
        tp=0;
        stk[0]=mn(0,0,0);
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            int in;
            scanf("%d",&in);
            node t=mn(in,i,i);
            sum[i]=sum[i-1]+in;
            while(tp&&t.n<=stk[tp].n)
            {
                t.l=stk[tp].l;
                stk[tp-1].r=stk[tp].r;
                ck(stk[tp]);
                tp--;
            }
            stk[++tp]=t;
        }
        while(tp)
        {
            stk[tp-1].r=stk[tp].r;
            ck(stk[tp]);
            tp--;
        }
        //printf("%d
",sum[0]);
        printf("%lld
%d %d
",an,al,ar);
    }
    return 0;
}

POJ 2559 Largest Rectangle in a Histogram
이 문 제 는 지난 문제 보다 feel good 가 더 쉬 워.. 터 지지 않도록 주의해..

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;

struct node
{
    int h;
    int l,r;
}stk[100005];
int top;
LL ans;

LL calc(node t)
{
    return (LL)t.h*(t.r-t.l+1);
}

void insert(node &t)
{

    while(top&&stk[top-1].h>=t.h)
    {
        top--;
        stk[top-1].r=stk[top].r;            ///    ,    
        t.l=stk[top].l;
        ans=max(calc(stk[top]),ans);
    }
    stk[top++]=t;
}

int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        ans = top = 0;
        node t;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&t.h);
            t.l=t.r=i;
            insert(t);
        }

        while(top--)                        ///pop    
        {
            stk[top-1].r=stk[top].r;
            ans=max(calc(stk[top]),ans);
        }
        printf("%lld
",ans);
    }
    return 0;
}