NYOJ 79 & 17 & 214 단조로운 최장자 서열 문제 (DP)

일단 서열이 뭔지 설명해 봐.만약 a 서열이 그 중 몇 개의 원소를 삭제한 후 b 서열과 완전히 같다면 b는 a의 하위 서열이라고 한다.
다음 두 가지 시나리오를 사용하여 단일 시퀀스 {An}이 존재한다고 가정합니다.
1.a(n+1)>a(n) .이때 a(n+1)는 An 서열의 끝에 추가하여 새로운 단조로운 서열을 형성할 수 있고 이 서열의 길이는 이전 An의 길이보다 크다.
2.a(n+1)<=a(n).이때 a(n+1)는 당연히 An 서열의 끝에 추가할 수 없다.
분석을 통해 우리는 이러한 결론을 얻을 수 있다. 하나의 단조로운 서열과 그 뒤의 원소의 관계는 이 서열의 끝 원소와만 관련이 있다.
이렇게 해서 이 문제는 다음과 같은 dp 해법이 생겼다.
1차원 그룹 dp[]를 만들고 dp[i]로 길이가 i인 단조로운 서열의 끝 요소의 값을 저장하며 top로 단조로운 서열의 최대 길이를 저장합니다.
초기 top=1, dp[1]=a1;
그런 다음 순서 An(i:2~n)을 뒤로 이동합니다.분명히 우리는 두 가지 상황에 직면하게 될 것이다.
1.a[i] > dp[top].이때 우리는 a[i]를 길이가 top인 단조로운 서열에 넣었다. 이때 서열의 길이는 top+1이고 top값도 따라서 업데이트된다. 즉, dp[++top]=a[i].
2.a[i]<=dp[top].이때 a[i]는 길이가 top인 단조로운 서열을 추가할 수 없습니다. 그러면 길이가 얼마나 되는 서열을 넣어야 합니까?
방법은 뒤에서 앞으로 dp[](j:top-1~1)을 옮겨다니며 조건을 충족시킬 때까지 a[i]>dp[j], 이때 단계 1과 유사하게 a[i]를 길이가 j인 단조로운 서열에 추가할 수 있다. 이때 이 서열의 길이는 j+1이다.
우리는 dp[j+1]의 값을 a[i]로 업데이트할 것이다.그런데 왜 업데이트를 해야 하나요?
a[i]는 반드시 dp[j+1]보다 작기 때문이다.왜 그랬을까?만약 a[i]가 dp[j+1]보다 작지 않다면, 우리가 찾은 j는 j+1이지 j가 아니다.그렇다면 우리는 왜 dp[j+1]의 최소치를 보류해야 합니까?
같은 길이의 단조로운 점증 서열에 있어 말미 원소의 값이 작을수록 그 후 원소가 이 서열에 들어갈 가능성이 높기 때문이다. 즉, 우리가 이렇게 하는 것은 분실을 방지하기 위한 최선의 방법이다.
그중의 오묘함은 독자가 한두 조의 데이터를 써서 위의 절차에 따라 체험할 수 있으니 너무 약한 데이터를 내지 마세요.O(∩_∩)O
따라서 우리는 시간의 복잡도가 O(n*n)인 코드를 다음과 같이 쓰기 쉽다.

#include <stdio.h>
#include <string.h>
int main()
{
    int z,n,num[21],dp[21];
    scanf("%d",&z);
    while(z--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&num[i]);
        int top=1;
        dp[1]=num[0];
        for(int i=1;i<n;i++)
        {
            if(num[i] > dp[top])
            {
                dp[++top] = num[i];
            }
            else
            {
                int j;
                for(j=top-1;j>=1;j--)
                    if(num[i] > dp[j])
                        break;
                dp[j+1] = num[i];
            }
        }
        printf("%d
",top);
    }
    return 0;
}

우리는 이미 답을 얻었다. 그렇다면 우리는 계속해서 시간의 복잡도를 최적화할 수 있을까?
첫 번째 상황은 분명히 최적화할 필요가 없다. 그렇다면 두 번째 상황은 안 될까?
두 번째 상황에서 우리가 해야 할 일은 단조로운 서열 dp[]에서 가장 큰 j를 찾아서 a[i]>dp[j]를 만족시키는 것이다.'단조로운'것을 보고 당신은 무엇을 생각했습니까?맞아요, 2점이에요.
이렇게 하면 시간의 복잡도는 (N*logN)이 됩니다.

 
#include <stdio.h>
#include <string.h>
int BinarySearch(int *a,int left,int right,int x)    //      a[]    a[i]>=x   
{
    if(a[left] >= x)
        return left;
    while(left <= right)
    {
        int mid = (left+right)/2;
        if(a[mid] >= x)
            right = mid-1;
        else
        {
            left = mid+1;
            if(a[left] >= x)
                return left;
        }
    }
}
int main()
{
    int z,top,dp[10005];
    char num[10005];
    scanf("%d",&z);
    while(z--)
    {
        scanf("%s",num);
        dp[(top=1)]=num[0];
        int n=strlen(num);
        for(int i=1;i<n;i++)
        {
            if(num[i] > dp[top])
                dp[++top]  = num[i];
            else
                dp[BinarySearch(dp,1,top,num[i])] = num[i];
        }
        printf("%d
",top);
    }
    return 0;
}

오늘은 기분이 좋지 않으니 블로그를 한 편 쓰고 조용히 해라.만약 잘못 썼다면 큰 소들의 양해를 바랍니다.