hdu 4521 샤 오 밍 시리즈 문제 - 샤 오 밍 시퀀스 (간격 이 적어도 d 인 LIS 두 가지 해법)

샤 오 밍 시리즈 문제 - 샤 오 밍 시퀀스
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1567    Accepted Submission(s): 463
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
   
   
   
   

 
Source
2013 텐 센트 프로 그래 밍 마라톤 1 차 전 4 차 전 (3 월 24 일)
제목:
길이 가 N 인 서열 을 지정 합 니 다. 현 재 는 가장 긴 서열 을 제시 하여 서열 중의 요 소 를 엄 격 히 상승 시 키 고 인접 한 두 숫자의 아래 표 시 된 간격 이 d 보다 엄 격 히 커 야 합 니 다.
사고방식 1:
LIS 변형, 추억 O (n * log (n) 의 해법, c [i] - 길이 i 의 증가 시퀀스 끝 에 있 는 최소 수 를 유지 합 니 다.c [] 에서 찾 을 때마다 > = a [i] 의 위치 pos, c [pos] 를 업데이트 하고 dp [i] = pos 를 얻 습 니 다.이제 인접 한 간격 > d 를 늦 추 려 면 d 개 단위 의 c [] 업데이트 만 늦 추 면 됩 니 다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 100005
#define OO (1<<31)-1
#define mod 90003
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,d,ans;
int a[MAXN],c[MAXN],dp[MAXN];

void solve()
{
    int i,j,t;
    ans=0;
    memset(c,0x3f,sizeof(c));
    for(i=1;i<=n;i++)
    {
        dp[i]=lower_bound(c+1,c+n+1,a[i])-c;
        ans=max(ans,dp[i]);
        j=i-d;
        if(j>0&&c[dp[j]]>a[j]) c[dp[j]]=a[j];
    }
}
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&d))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        solve();
        printf("%d
",ans);
    }
    return 0;
}

사고방식 2:
n * n 의 방법 은 dp [i] = max (dp [i], dp [j] + 1) 입 니 다.(a [i] > a [j]) 복잡 도 를 낮 추 려 면 라인 트 리 로 구간 a [i] 의 값 을 [l, r] 의 최대 dp 값 으로 유지 하면 됩 니 다. 매번 a [i], dp [i] 로 단일 업데이트, 구간 조회 할 수 있 습 니 다.인접 한 간격 > d 를 만 들 려 면 d 개 단위 의 업 데 이 트 를 지연 시 켜 야 합 니 다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 100005
#define OO (1<<31)-1
#define mod 90003
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,d,ans;
int a[MAXN],maxx[MAXN<<2],dp[MAXN];

int query(int le,int ri,int rt,int x,int y)
{
    if(le==x&&ri==y) return maxx[rt];
    int mid=(le+ri)>>1;
    if(y<=mid) return query(le,mid,rt<<1,x,y);
    else if(x>mid) return query(mid+1,ri,rt<<1|1,x,y);
    else
    {
        return max(query(le,mid,rt<<1,x,mid),query(mid+1,ri,rt<<1|1,mid+1,y));
    }
}
void update(int le,int ri,int rt,int x,int y)
{
    if(le==ri)
    {
        maxx[rt]=max(maxx[rt],y);
        return ;
    }
    int mid=(le+ri)>>1;
    if(x<=mid) update(le,mid,rt<<1,x,y);
    else update(mid+1,ri,rt<<1|1,x,y);
    maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
}
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&d))
    {
        memset(maxx,0,sizeof(maxx));
        ans=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i]+=2;
            dp[i]=query(1,100002,1,1,a[i]-1)+1;
            ans=max(ans,dp[i]);
            if(i-d>=1) update(1,100002,1,a[i-d],dp[i-d]);
        }
        printf("%d
",ans);
    }
    return 0;
}
/*
2 0
1 2
5 1
3 4 5 1 2
5 2
3 4 5 1 2
*/