[BZOJ1657] [Usaco 2006 Mar] 무우 젖소의 노랫소리(단조로운 창고)

2169 단어 단조 창고bzoj

제목 설명


전송문

문제풀이


처음 자세가 맞지 않아 황 선배의 자세를 배웠다.앞뒤 두 번 단조 창고.

코드

#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=5e4+5;
int n,top,ans;
int f[max_n],h[max_n],v[max_n];
struct stack{int h,v;}s[max_n];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&h[i],&v[i]);
    for(int i=1;i<=n;i++){
        while(top&&h[i]>s[top].h){
            f[i]+=s[top].v;
            top--;
        }
        s[++top].h=h[i];s[top].v=v[i];
    }
    top=0;
    for(int i=n;i>0;i--){
        while(top&&h[i]>s[top].h){
            f[i]+=s[top].v;
            top--;
        }
        s[++top].h=h[i];s[top].v=v[i];
    }
    for(int i=1;i<=n;i++)ans=max(f[i],ans);
    printf("%d",ans);
}

총결산


단조창고에서 다시 잘 생각해 봐.

좋은 웹페이지 즐겨찾기