hdu 1506 Largest Rectangle in a Histogram(동적 계획, 뛰어난 최적화)
1124 단어 동적 기획
a[i]에 대해 우리가 기록해야 할 것은 그의 이전과 이후의 가장 큰 연속 값이 a[i]보다 큰 길이이다. 만약에 매번 하나씩 비교해 보면 데이터 크기는 100000이고 시간 복잡도는 O(n^2)이다. 시간 초과는 필연적이다.그러나 사실 a[i]에 대해 말하자면 뒤에 있는 연속적인 값을 구하면 하나하나 비교할 필요가 없다. 직접 a[i+1]의 값을 보면 된다.
예를 들어 2, 3, 4, 5라는 서열을 보면 만약에 우리가 3이 뒤로 얼마나 길게 뻗을 수 있는지 보려면 4와 5를 비교할 필요가 없다. 4를 계산할 때 우리는 5가 4보다 크다고 계산했다. 왜냐하면 3은 4보다 작고 4가 뒤로 뻗을 수 있는 길이는 3도 반드시 도달할 수 있기 때문이다(4가 뻗을 수 있는 길이 내의 데이터는 모두 4보다 크고 물론 모두 3보다 크다). 우리는 4가 도달한 최종 길이의 끝에 있는 값을 직접 비교할 수 있다.
이 문제를 계산할 때 진법 변환도 각별히 주의해야 한다. 만약temp가 로 강제로 변환되지 않았다면int64비트, 제출회wa.
이 문제의 최적화된 사고방식은 매우 교묘하여 배울 만하다.
#include
#define N 100005
int a[N],s[N],e[N];
int main()
{
int n;
while(scanf("%d",&n),n)
{
int i;
for(i=0;i=1&&a[s[i]-1]>=a[i])
s[i]=s[s[i]-1];
}
for(i=n-1;i>=0;i--)
{
while(e[i]=a[i])
e[i]=e[e[i]+1];
}
__int64 ans;
ans=0;
for(i=0;ians)
ans=temp;
}
printf("%I64d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
