최대 단조로운 하위 시퀀스(DP)

12679 단어 dp
문제 설명: 한 그룹의 무질서한 수를 정하고 그 중에서 가장 긴 단조 서열의 길이(이 단조 서열은 반드시 연속적인 것이 아니다)를 구한다. 예를 들어 5, 6, 1, 2, 4, 7에서 가장 긴 상승 증가 서열은 1, 2, 4, 7 또는 1, 2, 4, 5이다.
이 문제는 동적 기획의 방법으로 해결할 수 있으며 시간의 복잡도는 O(n^2)이다.
A[t]를 설정하면 서열의 t번째 수를 표시하고 F[t]는 1에서 t까지의 단락에서 t로 끝나는 가장 긴 상승 서열의 길이를 나타낸다.
동적 기획 방정식: F[t]=max{1, F[j]+1}, 그 중에서 (j=1, 2,..., t-1, 그리고 A[j]=상기 공식을 통해 가장 긴 상승 서열의 길이를 max(F(t))로 구한다.
printResultSeq 함수는 귀속 방법을 통해 모든 최장자 서열을 출력합니다.
참조 코드:
 1 //seq：            ，(      );

 2 //len：        ;

 3 //tmpresult：          ;

 4 //end： F      tmpresult   ，     [0,end);

 5 //A:    ;

 6 //F :          F;

 7 void printResultSeq(int A[],int F[],int end,int tmpresult,int seq[],int len)

 8 {

 9     for(int i=0;i<end;i++)

10     {

11         if(tmpresult==F[i] && A[i]<=seq[tmpresult+1])

12         {

13             seq[tmpresult]=A[i];

14             if(tmpresult==1)

15             {

16                 for(int k=1;k<=len;k++)

17                     cout<<seq[k]<<",";

18                 cout<<"end"<<endl;

19                 return;

20             }

21             

22             printResultSeq(A,F,i,tmpresult-1,seq,len);

23 

24         }

25     }

26 }

27 

28 int fun( int A[] ,int n)

29 {

30     int *F=new int[n+1];

31     int result=0;

32     F[0]=1;

33     for(int i=1;i<n;i++)

34     {

35         F[i]=1;

36         for(int j=0;j<i;j++)

37         {

38             if(A[i]>=A[j])

39                 F[i]=max(F[i], F[j]+1);

40         }

41         if(result<F[i])

42             result=F[i];

43     }

44 

45     //////////////////print all result

46     int *seq=new int[result+2];

47     seq[result+1]=numeric_limits<int>::max(); //the max of int 

48     printResultSeq(A, F, n, result,seq,result);

49 

50     return result;

51 }

 
---------------------------------------------------------------------------
다음은 개선된 O(nlogn) 알고리즘입니다.
우리는 F[t]를 계산할 때의 상황을 자세히 고려했다.요소 A[x]와 A[y]가 두 개 있다고 가정하면 (1) x < y < t
(2)A[x] < A[y] < A[t]
(3)F[x] = F[y]
이때 F[x]를 선택하는 것과 F[y]를 선택하는 것은 모두 같은 F[t]값을 얻을 수 있다. 그러면 가장 긴 상승자 서열의 이 위치에서 A[x]를 선택해야 하나요, 아니면 A[y]를 선택해야 하나요?
분명히 A[x]를 선택하는 것이 A[y]를 선택하는 것보다 낫다.조건 때문에 A[x+1]에서...A[t-1] 이 단락에 A[z], A[x] 이상의 분석에서 우리는 다음과 같은 결론을 얻었다.
만약 우리가 A[0:t-1]의 가장 긴 단조로운 상승자 서열의 길이가 k이고 모든 길이가 k인 상승자 서열 중 마지막 요소의 최소값(b[k]이라고 기록)을 알고 있다면 우리의 관건은 이 수조 b[]를 유지하는 것이다.
그러면 A[t]>=b[k]이면 A[0:t]의 가장 긴 단조로운 상승자 서열의 길이는 k+1이고 b[k+1]=A[t];(결론1)
A[t]만약에 b[1]=참조 코드:
 1 int binary(int b[],int k,int key)

 2 {

 3     if(key<b[1])return 1;

 4     int low=1,high=k;

 5     while(low!=high-1)

 6     {

 7         if( b[k=(low+high)/2] <= key )low=k;

 8         else high=k;

 9     }

10     return high;

11 }

12 

13 int fun2(int A[] ,int n)

14 {

15     int *b=new int[n+1],k=1;

16     b[1]=A[0];

17     for(int i=1;i<n;i++)

18     {

19         if(A[i]>=b[k])b[++k]=A[i];

20         else b[binary(b,k,A[i])]=A[i];

21     }

22     return k;

23 }

이 알고리즘이 어떻게 모든 결과를 인쇄하는지에 대해 아직 연구하지 않았다??????
 
또 다른 방법은 먼저 원수 그룹의 정렬을 A1로 한 다음에 A와 A1의 가장 긴 공통 서열을 구하는 것이다
 
프로그래밍의 아름다움을 참고할 수 있는 2.16 구수조 중 가장 긴 체증자 서열
[판권 성명] 전재는 출처를 밝혀 주십시오http://www.cnblogs.com/TenosDoIt/archive/2013/04/19/3031589.html
내비게이션 해달래요.
제11회 산동성 대학생 프로그램 설계 경연대회 Adventurer's Guild(dp)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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