hdu 4521 샤 오 밍 시리즈 문제 - 샤 오 밍 서열 (구 간격 이 d 보다 긴 상승 서열)

3599 단어
샤 오 밍 시리즈 문제 - 샤 오 밍 시퀀스
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2697    Accepted Submission(s): 831
Problem Description
샤 오 밍 은 서열 과 관련 된 문 제 를 연구 하 는 것 을 가장 좋아 한 다 는 것 을 모두 가 알 고 있 지만 그 렇 기 때문에 샤 오 밍 은 각종 서열 문 제 를 거의 다 해 보 았 다.불쌍 한 샤 오 밍 은 각 사이트 에서 새로운 서열 문 제 를 찾 고 있 지만 찾 아 다 니 는 것 은 모두 자신 이 이미 연구 한 서열 이다.샤 오 밍 은 찾 을 수 없 으 니 스스로 새로운 서열 문 제 를 발명 하 라 고 생각 했다.샤 오 밍 은 생각 하고 생각 하 다가 마침내 새로운 서열 문 제 를 생각해 냈 다. 그 는 미 친 듯 이 기뻐 했다. 자신 이 생각 한 것 이기 때문에 새로운 서열 문 제 를 '샤 오 밍 서열' 이 라 고 명명 했다.
샤 오 밍 서열 을 언급 하면 그 가 내 린 정 의 는 다음 과 같다.
① 먼저 S 를 질서 있 는 서열 로 정의 하고 S = {A1, A2, A3,..., An}, n 을 요소 갯 수 로 한다.
② 그 다음 에 Sub 를 S 에서 꺼 낸 키 시퀀스 로 정의 합 니 다. Sub = {Ai 1, Ai 2, Ai 3,..., Aim}, m 를 요소 개수 로 정의 합 니 다.
③ 그 중 하위 만족 Ai1 < Ai2 < Ai3 <... < Aij - 1 < Aij < Aij + 1 <... < Aim;
④ 동시에 Sub 는 임의로 연 결 된 두 개의 Aij - 1 과 Aij 모두 ij - ij - 1 > d (1 < j < = m, d 가 주어진 정수) 를 만족 시 킵 니 다.
⑤ 이러한 Sub 서브 서열 을 만족 시 키 는 것 이 분명 하 다. 그러나 이 서브 서열 Sub 에서 요소 의 개 수 를 가장 많이 '소명 서열' (즉 m 에서 가장 큰 Sub 서브 서열) 이 라 고 부른다.
예 를 들 어 시퀀스 S = {2, 1, 3, 4}, 그 중 d = 1;
'소명 서열' 을 얻 을 수 있 는 m = 2.즉 Sub = {2, 3} 또는 {2, 4} 또는 {1, 4} 은 모두 '소명 서열' 이다.
샤 오 밍 이 '샤 오 밍 서열' 을 발명 하 는 순간 감정 이 매우 흥분 되 어 머리 가 혼 란 스 러 웠 다. 그래서 그 는 그 에 게 주어진 S 서열 과 정수 d 의 상황 에서 '샤 오 밍 서열' 중의 요 소 는 몇 개가 필요 한 지 계산 해 달라 고 부탁 했다.
 
Input
파일 이 끝 날 때 까지 데이터 여러 그룹 을 입력 하 십시오.
입력 한 첫 번 째 행동 은 두 개의 정수 n 과 d 입 니 다.(1<=n<=10^5 , 0<=d<=10^5)
입력 한 두 번 째 행위 n 개 정수 A1, A2, A3,..., An 은 S 서열 의 n 개 요 소 를 나타 낸다.(0<=Ai<=10^5)
 
Output
각 그룹의 데이터 출력 '소명 시퀀스' 의 요소 에 몇 개가 필요 합 니까? 각 그룹의 테스트 데이터 출력 줄 에 한 줄 씩 필요 합 니 다.
 
Sample Input 

   
   
   
   

    
    
    
    2 0
1 2
5 1
3 4 5 1 2
5 2
3 4 5 1 2

 
Sample Output 

   
   
   
   

    
    
    
    2
2
1

사고의 방향
:maxv
배열 이 유지 하 는 것 은 어떤 값 으로 끝 나 는 가장 긴 상승 서브 시퀀스 가 얼마 입 니까?
,
선분 나무의 템 플 릿 문제.
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100100;
int a[maxn],maxv[4*maxn],ANS[maxn];
int L,R,pos,v;

void pushup(int rt){
    maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
}

void update(int l,int r,int rt){
    if(l==r){
        maxv[rt]=max(maxv[rt],v);
        return ;
    }
    int m=(l+r)>>1;
    if(pos<=m)
        update(lson);
    else
        update(rson);
    pushup(rt);
}

int query(int l,int r,int rt){
    if(L<=l&&R>=r)
        return maxv[rt];
    int m=(l+r)>>1;
    int ret=0;
    if(L<=m)
        ret=max(ret,query(lson));
    if(R>m)
        ret=max(ret,query(rson));
    return ret;
}

int main(){
    int n,d;
    while(scanf("%d%d",&n,&d)!=EOF){
        int E=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]),a[i]++;
            E=max(E,a[i]);
        }
        memset(maxv,0,sizeof(maxv));
        int ans=1;
        for(int i=1;i<=n;i++){
            L=1,R=a[i]-1;
            if(L>R)
                ANS[i]=1;
            else
                ANS[i]=query(1,E,1)+1;
            ans=max(ANS[i],ans);
            if(i>d){
                pos=a[i-d],v=ANS[i-d];
                update(1,E,1);
            }
        }
        printf("%d
",ans);
    }
    return 0;
}
/*
4 3
0 0 0 1
*/
Django 템플릿-템플릿 상속
VMware Fusion에서 Windows 5 버튼 마우스를 사용하는 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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