[원] POJ-1631-Bridging signals-(물 LIS-O(nlogn)-DP)

제목 대의: 가장 긴 상승자 서열(LIS) 길이를 구하고 서열의 최대 수는 40000을 넘지 않습니다.상승 배열된 인터페이스만 교차하지 않기 때문이다.
사고방식: 일반적인 O(n^2)의 방법은 틀림없이 시간을 초과할 것이다.따라서 dp[]의 기록 길이가 i+1인 하위 서열 중 가장 마지막 원소의 최소값은 이 수조는 단조롭게 증가하기 때문에 dp[]수조 내의 원소는 2분 검색으로 dp[]에서 a[i]보다 큰 가장 작은 원소의 위치를 찾을 수 있다.여기에 STL 클래스의 로워를 사용했습니다bound(x, x+n, k) 함수(http://www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound 함수는 정렬된 서열 x[]에서 x[i]>=k를 만족시키는 x[i]의 최소 지침을 되돌려줍니다.
AC 코드는 다음과 같습니다.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define M 40010
#define INF 1000000
int dp[M],a[M];
void init(int *a, int n)
{
  for(int i = 0; i < n; i++)
  {
    a[i] = INF;
  }
}

int main()
{
  int n;
  scanf("%d",&n) == 1;
  while(n--)
  {
    int x;
    scanf("%d",&x);
    for(int i = 0; i < x; i++)
      scanf("%d",&a[i]);
    init(dp,x);
    for(int i = 0; i < x; i++)
      *lower_bound(dp, dp+x, a[i]) = a[i];
    cout<<lower_bound(dp, dp+x, INF) - dp<<endl;
  }
  return 0;
}

저자: u011652573 2014-3-6 14:58:03
텍스트 링크
읽기: 51 설명: 0
의견 보기