POJ 1887 Testing the CATCHER (LIS: 최 장 하강 서브 시퀀스)

POJ 1887 Testing the CATCHER (LIS: 최 장 하강 서브 시퀀스)
http://poj.org/problem?id=3903
제목:
       n (n < = 20000) 길이 의 숫자 서열 을 드 리 겠 습 니 다. 이 서열 에서 가장 긴 (엄격 한) 하위 서열 의 길 이 를 낮 추 십시오.
분석:
       모든 입력 을 읽 고 원본 배열 을 역방향 으로 한 다음 에 가장 길 고 엄격하게 하위 서열 을 올 리 면 됩 니 다.
       n 의 규모 가 20W 에 달 하기 때문에 O (nlogn) 의 알고리즘 으로 만 구 할 수 있 습 니 다.
       g [i] = = x 는 현재 옮 겨 다 니 는 길이 가 i 인 모든 최 장 상승 서브 시퀀스 의 최소 시퀀스 끝 값 을 x 로 표시 합 니 다. (지금까지 긴 i 의 상승 시퀀스 가 존재 하지 않 았 다 면 x = = INF 무한대)
       현재 j 의 첫 번 째 값 인 a [j] 를 옮 겨 다 녔 다 고 가정 하면 g [n] 배열 의 값 a [j] 의 하 확 계 (즉 첫 번 째 > = a [j] 값 의 g [k] 의 k 값) 를 먼저 찾 습 니 다. 그러면 이때 길이 가 k - 1 인 최 장 상승 서브 시퀀스 가 존재 하고 이 시퀀스 의 끝 위치 < j 와 이 시퀀스 의 끝 값 < a [j] 가 존재 한 다 는 것 을 나타 냅 니 다.
       그러면 우 리 는 g [k] = a [j] 와 dp [i] = k (dp 의 미 는 해법 1) 와 같다.
       (위 에서 시간 을 들 여 자세히 이해)
       최종 적 으로 우 리 는 아래 표 시 된 가장 큰 i 를 찾 아 낼 수 있 습 니 다. g [i] < INF 에서 i 가 가장 큽 니 다. 이것 이 바로 LIS 의 길이 입 니 다.
AC 코드: O (n * logn) 복잡 도
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000+5;
const int INF=1e8;

int n;
int a[maxn];
int g[maxn];

int main()
{
    int kase=0;
    while(scanf("%d",&a[1])==1 && a[1]!=-1)
    {
        if(kase>0) printf("
"); n=2; while(scanf("%d",&a[n])==1 && a[n]!=-1) { n++; } n--; reverse(a+1,a+n+1); for(int i=1;i<=n;i++) g[i]=INF; int ans=0; for(int i=1;i<=n;i++) { int k=lower_bound(g+1,g+n+1,a[i])-g; g[k]=a[i]; ans=max(ans,k); } printf("Test #%d:
maximum possible interceptions: %d
",++kase,ans); } return 0; }

좋은 웹페이지 즐겨찾기