[dp] 최장 증가 하위 시퀀스 poj 1631Bridging signals

poj 1631Bridging signals Dp(최대 증가 하위 시퀀스)
Bridging signals Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8689 Accepted: 4712 Description ‘Oh no, they’ve done it again’, cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without crossing each other, is imminent. Bearing in mind that there may be thousands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?
A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do. Input On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p < 40000, the number of ports on the two functional blocks. Then follow p lines, describing the signal mapping:On the i:th line is the port number of the block on the right side which should be connected to the i:th port of the block on the left side. Output For each test scenario, output one line containing the maximum number of signals which may be routed on the silicon surface without crossing each other. Sample Input 4 6 4 2 6 3 1 5 10 2 3 4 5 6 7 9 10 1 8 8 7 6 5 5 4 4 3 2 1 9 5 8 9 2 3 1 7 4 6 Sample Output 3 9 1 4 Source Northwestern Europe 2003 문제: 1 개의 서열을 정하고 중복되지 않으며 x가 y 위치에 나타나는 것은 x와 y가 연결될 수 있음을 의미한다.마지막으로 이 서열에서 가능한 한 많은 연결을 선택하고 연결이 교차하지 않도록 해야 한다.문제풀이 사고방식: 사실 이 문제는 두 서열의 연결선으로 연결선이 교차하지 않는 가장 많은 연결 수를 구하는 것이다.이 문제는 하나의 서열이 이미 고정되어 있기 때문에 다른 열이 선택한 수가 점차적으로 늘어나는 것을 보장하면 교차하지 않을 것이다. 이해하지 못하면 몇 개의 시뮬레이션을 그려 보면 알 수 있다.그 문제는 최장 증자 서열로 바뀌었다.일반적인 해법의 시간 복잡도는 n^2이지만 이 문제는 데이터가 비교적 커서 더욱 효율적인 해법이 필요하다.매번 업데이트의 가장 긴 시퀀스 길이는 기존의 길이에 따라 달라지기 때문에, 이 과정을 하나의 수조로 모의해 보십시오. 수조 아래에 표시된 길이는 길이이고, 수조 내용은 현재 길이가 가장 작은 수치를 나타냅니다.이렇게 답안을 갱신하려면 아래 표시가 가장 큰 곳부터 비교하면 된다.길이가 점차 늘어나기 때문에, 매번 업데이트되는 하표를 이분으로 찾을 수 있다.
기본 사상: dp가 m[i]를 설정하면 {1,2,...,i}의 최장이 서열의 길이를 낮추지 않고 0<=j<=i-1,data[i]>data[j]에 비칠 때 m[i]=max(m[j],m[j]+1)가 있다.알고리즘 복잡도 O (n^2)
기교: 하나의 수조 a[i]를 설정하여 모든 길이가 i인 상승자 서열 중 가장 작은 마지막 원소 값을 저장한다. 예를 들어 두 개의 길이가 3인 상승자 서열 123과 124만 저장하면 a[3]에 저장된 것은 3(마지막 원소 3<4)이다.그러면 새로운 데이터 데이터가 올 때 가장 긴 마지막 요소의 값(즉 a[ans])보다 값이 크면ans++;그리고 a[ans]=데이터;그렇지 않으면, 이분 검색 (수조 a의 원소는 증가함) 을 통해 데이터에 가장 가깝고 데이터보다 큰 원소를 데이터로 업데이트합니다.예를 들어 1,5,3,4, 그 다음에 2,a[1]=1,a[2]=3,a[3]=4;a[2]=2 업데이트하기;이분 검색의 복잡도는log(n)이고 외곽은 n이기 때문에 전체적인 복잡도는 nlogn이다

#include 
int res[40000];
int binSearch(int left, int right, int num)         //            
{
    while(left <= right)
    {
        int mid=(left + right)/2;
         if(res[mid]1;
        else  right=mid-1;
    }
    return right;
}
int main()
{
    int t, n, num;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &num);
        res[0]=num;
        int tot = 1;
        for(int i=1;i"%d", &num);
            if(num>=res[tot-1])
            res[tot++]=num;
            else
            {
                int pos=binSearch(0,tot-1,num);      //          
                res[pos+1] = num;
            }  
        }
        printf("%d
", tot);
    }
    return 0;
}

댓글을 남기고 적극적으로 토론하며 함께 진보하는 것을 환영합니다!