Poj 3264: Balanced Lineup - 문제 풀이 + st 표 해석

2498 단어 pojdp제목 집계st 표데이터 구조
poj 3264
이 문 제 는 사실 그 자체 가 어렵 지 않 습 니 다.구체 적 으로 무엇 일 까요? 그 중의 i 는 출발점 을 대표 하고 2 ^ j 는 출발점 에서 중심 까지 의 길 이 를 대표 합 니 다.아직 모 르 시 면 샘플 (최소 값 구하 기) 2, 6, 4, 8, 9, 7, 11 을 살 펴 보 겠 습 니 다. 좋 습 니 다. 프로그램의 운영 dp [1] [0] = 2 를 모 의 해 보 겠 습 니 다.dp[2][0]=6……dp[7][0]=11; 그리고 dp [1] [1] = min (2, 6) = 2;dp[3][1]=min(4,8)=4;……dp[6][1]=min(7,11)=7; 그리고 dp [1] [2] = min (2, 4) = 2;...이러이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러 이러그 다음 에 조 회 했 습 니 다. 그러나 가끔 은 조회 구간 이 비교적 커서 한 걸음 에 도착 하지 못 할 때 가 있 습 니 다. 예 를 들 어 1 - 5 구간 을 조회 하 는 것 입 니 다. 그러나 우리 위의 정의 에 따라 우 리 는 최대 dp [1] [2] 를 호출 할 수 있 지만 다섯 번 째 점 이 떨 어 졌 습 니 다.사실 아주 간단 합 니 다. 결과 = min (dp [1] [2], dp [2] [2]) 원인 도 설명 할 필요 가 없 겠 죠? 그럼 코드 로 이 루어 지 는 김 에 이 문 제 를 쓰 겠 습 니 다.
#include
#include
#include
#include
#include
using namespace std;
int maxn[50001][30],minn[50001][30];
int qpow(int a){
    return (1<void st(int n){
for(int j=1;j<=int(log2(n));j++){
for(int i=1;i<=n;i++){
int p=i+pow(2,j)-1;
if(p>n)continue;
maxn[i][j]=max(maxn[i][j-1],maxn[i+int(qpow(j-1))][j-1]);
minn[i][j]=min(minn[i][j-1],minn[i+int(qpow(j-1))][j-1]);
}
}
return;
}
int main(){
int n,q,k,x,y;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&maxn[i][0]);
minn[i][0]=maxn[i][0];
}
st(n);
for(int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
if(yint t=x;x=y;y=t;
}
double s=y-x+1;
int ke=log2(s);
int he=qpow(int(log2(s)));
int t1=max(maxn[x][int(log2(s))],maxn[y-he+1][ke]);
int t2=min(minn[x][int(log2(s))],minn[y-he+1][ke]);
printf("%d",t1-t2);
}
return 0;
}
python 기초 문법 및 여러가지 알아두면 좋을 것들
BOJ 2136 개미

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage