[BZOJ1657] [Usaco 2006 Mar] 무우 젖소의 노랫소리(단조로운 창고)
제목 설명
전송문
문제풀이
처음 자세가 맞지 않아 황 선배의 자세를 배웠다.앞뒤 두 번 단조 창고.
코드
#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);
}
총결산
단조창고에서 다시 잘 생각해 봐.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ2796 - Feel Good - 단조로운 대기열(dp사상)His recent investigations are dedicated to studying how good or bad days influent people's memories about some period of...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.