최 장 상승 서브 시퀀스 O (n * lg (n)) 코드

문제 설명: 하위 서열 이란 원래 서열 에서 몇 개의 요 소 를 삭제 한 후에 남 은 서열 입 니 다. 문자열 'abcdefg' 을 예 로 들 어 bde 를 제거 하고 하위 서열 인 'acfg' 를 얻 는 것 입 니 다. 현재 문 제 는 숫자 서열 을 주 는 것 입 니 다. 가장 긴 단조 로 운 서브 서열 을 요구 하 는 것 입 니 다.
입력: 여러 조 의 테스트 데이터, 각 조 의 테스트 데이터 첫 줄 은 n (1 < = n < = 10000) 이 고, 다음 줄 은 n 개가 1e9 보다 작은 비 마이너스 정수 입 니 다.
출력: 각 그룹의 테스트 데이터 출력 줄 에 대해 각 줄 의 내용 은 가장 긴 단조 로 운 증가 서브 시퀀스 의 길이 입 니 다.
샘플 입력: 5 1 2 4 8 16 5 1 10 4 9 0 1 1 5 5
샘플 출력: 5, 3, 3
[분석]
처음에 이 문 제 를 받 으 면 미사일 (최 장 상승 서브 시퀀스) 이라는 문제 의 원형 변종 이 라 고 생각 하기 쉬 워 서 쉽게 생각 할 수 있 는 사고 가 있다. 즉, 동태 계획 이다.Length [i] 를 설정 하면 시퀀스 Seq 에서 Seq [i] 를 마지막 요소 로 할 때의 증가 시퀀스 의 길 이 를 나 타 냅 니 다.다음 과 같은 상태 전이 방정식 이 있 습 니 다. Length [i] = max {Length [j] | 0 < = j < = i - 1 and Seq [j] < Seq [i]} (1 < = i < n) 경계 조건: Length [i] = 1 (0 < = i < n).그래서 다음 과 같은 실현 코드 가 있 습 니 다. vector < int > Length (n, 1);for (size t i = 1; i < Seq. size (); i + +) {Max = 0; for (size t j = 0; j < i; j +) if (Seq [j] & & Length [j] > Max) Max = Length [j]; Length [i] = Length [i] + Max;} Length 의 최대 치 는 서열 Seq 의 최 장 증자 서열 의 길이 입 니 다.분명히 이것 은 T (n) = O (n ^ 2) 의 알고리즘 이다.그 당시 에 저 는 이 생각 으로 쓴 코드 를 제출 했 습 니 다. 그 결과 마지막 데이터 가 시간 을 초과 한 것 은 상기 알고리즘 의 효율 이 요구 에 부합 되 지 않 았 음 이 분명 합 니 다.위의 알고리즘 에서 모든 Length [i] 를 계산 할 때 가장 큰 Length [j] (j < i) 를 찾 아야 합 니 다. Length 는 무질서 하고 순서대로 만 찾 을 수 있 습 니 다.이 순 서 를 2 분 검색 으로 바 꿀 수 있다 면 시간 복잡 도 는 O (n ^ 2) 에서 O (nlogn) 로 낮 아진 다.오랫동안 생각 했 지만 생각 이 없어 서 baidu 에 가서 생각 을 찾 았 습 니 다. 배열 Last 를 만들어 서 서브 시퀀스 의 마지막 요 소 를 저장 하고 Last [Length [j] = Seq [j - 1] 를 만 들 었 습 니 다. 이렇게 저장 하면 Last 중의 요 소 를 점차적으로 배열 할 수 있 습 니 다.따라서 위의 방법 에서 Length 에서 가장 큰 요 소 를 선형 으로 찾 아 Length 를 업데이트 하 는 작업 은 배열 Last 에서 2 분 으로 Last [k] < Seq [i] 를 만족 시 키 는 가장 큰 k 를 찾 고 Last [k + 1] 를 Seq [i] 로 설정 할 수 있 습 니 다.그래서 상태 전이 방정식 은 k = max {k | Last [k] < Seq [i]} (1 < = i < n) 경계 조건: Last [0] = INTMIN，Last[1]=Seq[1]。그렇다면 가장 직접적인 실현 방법 은 다음 과 같은 방법 2.전에 소 붕 의 사고방식 을 참고 하여 코드 (즉 아래 의 방법 1) 를 썼 기 때문에 방법 2 라 는 알고리즘 을 이해 한 후에 저 는 습관 적 으로 두 가지 알고리즘 을 비교 한 결과 이들 이 놀 라 울 정도 로 비슷 하 다 는 것 을 알 게 되 었 습 니 다!방법 1 중 set < T > 클래스 의 구성원 함수 insert (T val) 의 기능 은 정렬 삽입 과 유사 합 니 다. 정렬 삽입 요 소 를 삽입 하 는 과정 은 삽입 할 데 이 터 를 삽입 할 첫 번 째 데 이 터 를 삽입 할 배열 요소 보다 앞 에 삽입 하 는 것 입 니 다. 삽입 한 후에 마지막 에 삽입 하지 않 으 면 바로 다음 요 소 를 삭제 합 니 다.(즉, 삽입 요 소 를 마지막 에 두 지 않 으 면 오래된 데 이 터 를 교체 합 니 다) 이 는 두 번 째 방법 으로 배열 Last 에서 2 분 으로 Last [k] < Seq [i] 를 만족 시 키 는 가장 큰 k 를 찾 아 Last [k + 1] 를 Seq [i] 로 설정 하 는 것 과 같 습 니 다. 이 조작 은 공통점 이 있 습 니 다!
[Code]
방법 1:
#include
#include
using namespace std;
int main()
{
size_t n;
while (cin>>n)
{
set Last;
for (size_t i=0; i{
long Temp;
set::iterator Index;
cin>>Temp;
Last.insert(Temp);
Index=Last.find(Temp);
if (++Index!=Last.end()) Last.erase(Index);
}
cout<}
return 0;
}
방법 2:
#include
#include
using namespace std;
size_t LISLength(vector &Seq)
{
vector < long > Last (Seq. size () + 1); / Last [i] 를 마지막 요소 로 하 는 증가 서브 시퀀스 길 이 는 i 입 니 다.
size_t Length=1;
Last[0]=INT_MIN;
Last[1]=Seq[0];
for (size_t i=1; i{
size_t Front=0, Rear=Length, Middle;
while (Front < = Rear) / / 2 분 검색 끝 요소 가 Seq [i] 보다 작은 길이 의 증가 서브 시퀀스
{
Middle=(Front+Rear)/2;
if (Last[Middle]else Rear=Middle-1;
}
Last[Front]=Seq[i];
if (Front>Length) Length=Front;
}
return Length;
}
int main()
{
size_t n;
while (cin>>n)
{
vector Seq;
int Temp=0;
for (size_t i=0; i{
cin>>Temp;
Seq.push_back(Temp);
}
cout<}
return 0;
}
다음 코드 는 최 장 하강, 상승 하지 않 음, 하위 시퀀스 의 길 이 를 계산 하 는 것 으로 쉽게 수정 할 수 있 습 니 다. Last 초기 화 및 2 분 검색 시 머리 꼬리 지침 을 바 꾸 는 조건 일 뿐 입 니 다. 이 알고리즘 은 O (n ^ 2) 와 다른 점 은 이 알고리즘 이 교묘 하 게 상 태 를 바 꾸 어 2 분 검색 으로 효율 을 높 일 수 있 도록 하 는 것 입 니 다.
int LIS(const int *pcnSeq, int nLen) { int l=0, *pnLast=new int[nLen+1];
pnLast[0]=INT_MIN; for (int i=0; iwhile (p<=r) { int m=(p+r)/2;
if (pnLast[m]l) l=p; } delete[] pnLast; return l; }
먼저 전형 적 인 O (n ^ 2) 의 동적 계획 알고리즘 을 돌 이 켜 보고 A [t] 는 서열 중의 t 번 째 수 를 나타 내 고 F [t] 는 1 부터 t 까지 의 최 장 상승 서브 시퀀스 의 길 이 를 나타 내 며 초기 에 F [t] = 0 (t = 1, 2,..., len (A) 을 설정 합 니 다. 동적 계획 방정식: F [t] = max {1, F [j] + 1} (j = 1, 2,..., t - 1, 그리고 A [j] < t]) 가 있 습 니 다. 지금 우 리 는 F [t] 를 자세히 고려 하여 계산 합 니 다.시의 경우. 만약 에 두 가지 요소 A [x] 와 A [y] 가 있다 고 가정 하면 만족 (1) x < y < t (2) A [x] < A [t] (3) F [x] = F [y] 를 선택 할 때 F [x] 와 F [y] 를 선택 하면 똑 같은 F [t] 값 을 얻 을 수 있다. 그러면 가장 긴 상승 서브 시퀀스 의 이 위치 에서 A [x] 를 선택해 야 합 니까? 아니면 A [y] 를 선택해 야 합 니까? 분명 합 니 다. A [x] 를 선택 하 는 것 이 A [y] 를 선택 하 는 것 보다 좋 습 니 다. 조건 (2) 때문에 A [x] 를 선택해 야 합 니 다.[x + 1]... A [t - 1] 단락 에 A [z], A [x], A [z], a [y] 가 존재 한다 면 A [y] 를 선택 하 는 것 보다 더 긴 상승 서브 시퀀스 를 얻 을 수 있 습 니 다. 조건 (3) 에 따라 우 리 는 F [] 의 값 에 따라 분류 한 다 는 시사 점 을 얻 을 수 있 습 니 다. F [] 의 모든 수치 k 에 대해 우 리 는 F [t] = k 를 만족 시 키 는 모든 A [t] 의 최소 값 만 유지 해 야 합 니 다. D [k] 를 설정 하여 이 값, 즉 D [k] 를 기록 합 니 다.= min {A [t]} (F [t] = k). D [] 의 두 가지 특징 을 알 아 차 렸 습 니 다. (1) D [k] 의 값 은 전체 계산 과정 에서 단 조 롭 게 상승 하지 않 습 니 다. (2) D [] 의 값 은 질서 가 있 습 니 다. 즉, D [1] < D [2] < D [3] <... < D [n] 를 이용 합 니 다. D [] 를 이용 합 니 다., 우 리 는 가장 긴 상승 서브 시퀀스 의 길 이 를 계산 하 는 다른 방법 을 얻 을 수 있 습 니 다. 현재 구 한 가장 긴 상승 서브 시퀀스 의 길 이 를 len 으로 설정 합 니 다. 먼저 A [t] 와 D [len] 을 판단 합 니 다. 만약 A [t] > D [len] 이 라면 A [t] 를 D [len] 에 연결 한 후에 더 긴 상승 서브 시퀀스 를 얻 을 수 있 습 니 다. len = len + 1, D [len] = A [t]; 그렇지 않 으 면 D [1]. D [len] 에서 가장 큰 j 를 찾 아 D [j] < A [t] 를 만족 시 킵 니 다.. 령 k = j + 1 은 D [j] < A [t] < = D [k] 가 있 고, A [t] 를 D [j] 에 연결 하면 더 긴 상승 서브 시퀀스 를 얻 을 수 있 으 며, 동시에 D [k] = A [t] 를 업데이트 합 니 다. 마지막 으로, len 은 요구 하 는 가장 긴 상승 서브 시퀀스 의 길 이 를 얻 습 니 다. 상기 알고리즘 에서 소박 한 순 서 를 사용 하여 D [1]. D [len] 에서 찾 으 면, 모두 O (n) 개의 요 소 를 계산 해 야 하기 때문에 매번 계산 할 때의 복잡 도 는 O (n) 입 니 다.즉, 전체 알고리즘 의 시간 복잡 도 는 O (n ^ 2) 로 원래 의 알고리즘 에 비해 발전 이 없습니다. 그러나 D [] 의 특징 (2) 으로 인해 우리 가 D [] 에서 찾 을 때 2 분 검색 을 사용 하여 효율 적 으로 완성 할 수 있 으 며 전체 알고리즘 의 시간 복잡 도 는 O (nlogn) 로 떨 어 지면 서 매우 현저하게 향상 되 었 습 니 다. 주의해 야 할 것 은 D [] 입 니 다.알고리즘 이 끝 난 후에 기 록 된 것 은 문제 의 뜻 에 부합 되 는 최 장 상승 서브 시퀀스 가 아 닙 니 다. 이 알고리즘 은 전체 최 장 서브 시퀀스 문제 로 확장 할 수 있 습 니 다. 전체 알고리즘 의 난점 은 2 점 에서 찾 은 디자인 에 있 습 니 다. 매우 조심해 야 합 니 다.
ZOJ - 1866 문 제 를 참고 할 수 있 습 니 다.http://acm.zju.edu.cn/show_problem.php?pid=1986
solutiion for zoj 1986:
#include"stdio.h" unsigned int j,n,p,i,k1,k2,k3,len,a,D[40002]; int main(void) { scanf("%u",&n); while(n--) { scanf("%u",&p); len=0; for(i=1;i<=p;i++) { scanf("%u",&a); if(a>D[len]){ len++; D[len]=a; } else{ k1=0; k2=len; while(k2-k1>1){ k3=(k2+k1)/2; if(D[k3]>=a) k2=k3; else k1=k3; } D[k2]=a; } } printf("%u/n",len); } return 0; }
유 여 가 의 방법

 
 
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 1000005
using namespace std;

int a[N],d[N],g[N],n;
int lis()
{
    int i,j,ans=0;
    memset(d,0,sizeof(d));
    memset(g,1,sizeof(g));
    for(i=0;i<n;i++)
    {
        j=lower_bound(g,g+n,a[i])-g;
        d[i]=j+1;
        g[j]=a[i];
        ans=max(ans,d[i]);
    }
    return ans;
}
int main()
{
    int i;
    while(scanf("%d",&n)==1)
    {
        for(i=0;i<n;i++)
            scanf("%d",a+i);
        printf("%d/n",lis());
    }
}