학습 노트 - 간단 한 배증 알고리즘 - st 알고리즘
배가
st 알고리즘
배가 되 는 해석
배가 알고리즘 에 대해 말하자면 배로 증가 하여 생략 할 수 있 는 계산 을 뛰 어 넘 고 가속 효 과 를 얻 는 것 이다.
st 알고리즘
배가 되면 st 알고리즘 을 제시 하지 않 을 수 없다. 이것 은 아마도 배가 되 는 가장 전형 적 인 응용 일 것 이다.st 알고리즘 은 RMQ 문제 (구간 최대 값), 즉 하나의 서열 에서 수치 가 가장 큰 항목 을 구 하 는 데 적용 된다.소박 한 방법 은 자 연 스 럽 게 스 캔 을 통 해 최대 치 를 찾 는 것 이지 만 문제 의 질문 횟수 가 많 을 때 시간 을 초과 할 가능성 이 높 기 때문에 배증 알고리즘 으로 최적화 시킨다.
다음은 st 알고리즘 이 RMQ 문 제 를 해결 하 는 실현 입 니 다.
우선, 우 리 는 f [i] [j] 로 서열 a 에서 i 번 째 숫자 이후 2j 개 수의 최대 치 를 표시 하면 f [i] [0] = a [i] 를 얻 을 수 있다.
다음은 DP 과정 을 진행 합 니 다.
for(int j = 1;j <= ( log2(n) ); j++)
for(int i = 1;i <= n - (1 << j) + 1; i++)
f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
f [i] [j] 가 표시 하 는 구간 은 [i, i + 2j] 의 최대 치 이 고 2j = 2 * 2j - 1 = 2j - 1 + 2j - 1 이 므 로 우 리 는 구간 [i, i + 2j] 을 [i, i + 2j - 1] 과 [i + 2j - 1 + 1, 2j] 로 나 눌 수 있다.구간 을 두 부분 으로 나 눌 수 있 으 니 DP 의 사고방식 이 명확 해 지고 f [i] [j] 의 값 을 구 할 수 있다.
그러나 문제 가 묻 는 구간 이 꼭 2 의 멱 차방 이 아니 라 구간 을 초과 할 수 있다.
따라서 l 을 구간 길이 로 설정 하고 조회 할 때 k = log 2 (l) 를 구하 여 아래로 조정 할 수 있 습 니 다.
그러면: l / 2 < = 2k < = l
max (f [i] [k], f [i + 2j - 2k] [k]) 가 원 하 는 구간 의 최대 치 입 니 다.
처음 블 로 그 를 쓰 는데 잘 못 쓰 는 것 도 양해 해 주세요. 저녁 에 도 좀 졸 리 니까 코드 를 달 아 주세요.
Luogu P3865
#include
",max(f[l][k],f[r-(1<<k)+1][k]));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
셸 에서 expect 명령 을 사용 하여 원 격 명령 스 크 립 트 를 실행 합 니 다.1. 스 크 립 트 의 실행 방법 은 bash 셸 과 다 릅 니 다. 2. 한 스 크 립 트 에 파 라 메 터 를 전달 할 때 bash 셸 은 $1, 2... 파 라 메 터 를 받 습 니 다.한편, e x p e c...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
