최 장 단조 로 운 증가 서브 시퀀스 (동적 계획)
int 시퀀스 를 지정 하여 최 장 단조 로 운 증가 서브 시퀀스 를 구하 십시오.
1. 알고리즘 사상:
문제 변환: a 는 원시 서열 이 고 b 는 a 의 오름차 순 정렬 후의 서열 이 며 a 와 b 의 최 장 공공 서열 을 구한다.
2. 최 우선 서브 구조:
a 시퀀스 의 앞 i 개 요소 와 b 서열 의 전 j 개 요소 의 가장 긴 공공 서브 서열 은 반드시 a, b 의 가장 긴 공공 서브 서열 의 일부분 이다.
3. 상태 전이 방정식:
a 의 앞 i 개 요소 와 b 의 앞 j 개 요소 에 대해 t [i] [j] 는 공공 서브 시퀀스 의 최대 길이 이다.공공 하위 시퀀스 의 마지막 요 소 는 zx 입 니 다.
①a[i-1] = b[j-1] : t [i] [j] = t [i-1] [j-1] +1
마지막 요 소 는 같 습 니 다. zx 는 반드시 두 서열 의 마지막 요소 입 니 다.
②a[i-1] != b[j-1]: t [i] [j] = max(t[i-1][j], t[i][j-1])
마지막 요소 가 다 르 면 zx 는 a 의 전 i - 1 개 요소 와 b 의 전 j 개 요소 가 가장 긴 공공 서브 서열 의 마지막 요소 이거 나 a 의 전 i 개 요소 와 b 의 전 j - 1 개 요소 가 가장 긴 공공 서브 서열 의 마지막 요소 이다. 원래 문제 가 가장 좋 은 해결 이 필요 하기 때문에 길이 가 비교적 크다.
원문 제의 해: t [n] [n]
4. 실현:
그 중에서 m [i] [j] 는 t [i] [j] 가 어떤 서브 문제 로 얻 었 는 지 기록 하 는 데 사용 된다.최종 결 과 를 출력 할 때 제목 은 출력 이 단 조 롭 게 증가 하 는 최 장 서브 시퀀스 를 요구 하 므 로 같은 값 을 제외 해 야 합 니 다.(코드 중의 limit 는 이 점 을 나타 낸다)
int solve(int a[],int n){
int b[n],i,j;
int t[n+1][n+1],m[n+1][n+1];
for(i=0;it[i][j-1]?2:3;
}
}
}
i=n;j=n;
int sub[n],k=0,limit=MaxInt;
while(i>=0&&j>=0){
if(m[i][j]==1&&a[i-1]=0;i--)
cout< 5. 시간 복잡 도: O (n ＾ 2)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
