NYOJ 214 최장 상승 하위 시퀀스 강화 버전(2점+dp)

1399 단어 dp
수치 범위가 비교적 큰 n구해의 최장 상승 서열에 대해 폭력으로 비교하면 틀림없이 안 된다.그러면 우리는 하나의 dp수조로 이 가장 긴 서열을 표시할 수 있다. 그 아래 표시는 가장 긴 상승 서열을 대표하고 dp[top]의 값은 길이가 top인 수의 최소값을 만족시킨다.그리고 순서대로 전체 그룹 a[i]를 훑어본다.그리고 a[i]를 찾아 dp[]에 있는 위치를 찾고 l로 돌아가면 a[i]가 dp[]에 있는 상승 시퀀스 값을 나타낸다.dp[]와 같거나 적은 위치를 찾아 이 위치의 값을 a[]로 직접 부여한 다음 현재 최대 길이와 되돌아오는 위치의 관계를 비교합니다. 되돌아오는 값>현재 최대 길이가 되면 현재 최대 길이를 되돌아오는 길이로 변경합니다.
샘플 입력
7
1 9 10 5 11 2 13
2
2 -1

샘플 출력
5
1
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int a[1000000],dp[1000000],n;
int top;
int so(int x)
{
    int l=1,r=top;
    while(l<=r)
    {
       int mid=(l+r)>>1;
        if(dp[mid]==x)
            return mid;
        if(dp[mid]<x)
            l=mid+1;
        else
            r=mid-1;
    }
    return l;
}
int main()
{
    int m,i,j;
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        dp[1]=a[0];
        top=1;
        for(i=1;i<n;i++)
        {
            int tmp=so(a[i]);
            dp[tmp]=a[i];
            if(tmp>top)
                top=tmp;
        }
        printf("%d
",top);
    }
    return 0;
}
합법적인 괄호식의 최대 길이 구법 (우선순위가 없을 때)
위도 경도에서 지리원 타일을 다운로드하다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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