최 장 공공 상승 서브 시퀀스 의 DP 해법 및 최적화

최근 최 장 공공 상승 서브 시퀀스 에 대한 DP 방법 을 배 워 인터넷 에서 자 료 를 찾 아 봤 다.한편 으로 는 너무 어 지 러 워 서 다른 한편 으로 는 ICPC 에서 '왜' 를 알 고 '어떻게 하 는 지' 를 아 는 것 이 더 중요 하 다 고 생각 하기 때문에 스스로 정 리 를 썼 습 니 다.
정의 상태
F [i] [j] 는 a 열의 앞 i 개의 정수 와 b 열의 앞 j 개의 정수, 그리고 b [j] 를 끝으로 구 성 된 LCIS 의 길 이 를 나타 낸다.
상태 이동 방정식:
①F[i][j] = F[i-1][j] (a[i] != b[j])
②F[i][j] = max(F[i-1][k]+1) (1 <= k <= j-1 && b[j] > b[k])
지금 우리 가 말 하면 왜 이런 상태 전이 방정식 일 까?
① 에 대해 F [i] [j] 는 b [j] 로 끝 나 는 LCIS 이기 때문에 F [i] [j] > 0 이 라면 a [1]. a [i] 에 반드시 정수 a [k] 가 b [j] 와 같 고 a [k] 가 있 기 때문이다! =a [i], 그러면 a [i] 는 F [i] [j] 에 기여 하지 않 았 기 때문에 우 리 는 그것 이 F [i] [j] 의 최 우수 치 를 얻 을 수 있다 는 것 을 고려 하지 않 았 다.그래서 a [i]! =b [j] 의 경우 반드시 F [i] [j] = F [i - 1] [j] 가 있다.
② 에 대해 전 제 는 a [i] = b [j] 이다. 우 리 는 가장 길 고 b [j] 를 그 끝 에 연결 할 수 있 는 LCIS 를 찾 아야 한다.전에 제일 긴 LCIS 가 어디 있 었 죠?우선 우리 가 찾 아야 할 F 배열 의 1 차 는 반드시 i - 1 이다.i 가 이미 b [j] 와 짝 을 지어 갔 기 때문에 사용 할 수 없습니다.그리고 i - 2 일 수도 없습니다. i - 1 이 i - 2 보다 더 좋 을 수 밖 에 없 기 때 문 입 니 다.2 차원 은 요?그럼 b [1]... b [j - 1] 를 매 거 해 야 합 니 다. 이 중에서 어느 것 이 가장 길 고 어느 것 이 b [j] 보다 작은 지 모 르 기 때 문 입 니 다.여기에 또 하나의 문제 가 있 는데, 어 울 리 지 않 을 리 가 없 겠 는가?즉, a [i] = b [j] 의 경우 F [i] [j] = F [i - 1] [j] 의 결정 을 고려 할 필요 가 있 습 니까?답 은 필요 없다.만약 에 b [j] 가 a [i] 와 짝 짓 지 않 는 다 면 그것 은 바로 이전의 a [1]... a [j - 1] 와 짝 짓 기 (F [i - 1] [j] > 0 을 가정 하면 0 을 고려 하지 않 는 것 과 같다) 이기 때문에 a [i] 와 짝 짓 기 가 좋 지 않 을 것 이다.(왜 필연 적 일 까? b [j] 와 a [i] 가 짝 을 이 룬 후의 이전 은 max (F [i - 1] [k] + 1 이 고, 이전의 i '와 짝 을 이 룬 것 은 max (F [i' - 1] [k] + 1 이기 때문이다.
소박 한 LCIS 알고리즘 구현
Hdu 1423 Greatest Common Increasing Subsequence 를 예 로 들 면.
전처리:
핵심 코드:
4. 567913. 이상 의 코드 의 시간 복잡 도 는 O (n ^ 3) 입 니 다. 그러면 우 리 는 어떻게 최적화 할 수 있 습 니까? 생각 을 통 해 3 층 순환 에서 최대 치 를 찾 으 면 최적화 할 수 있 습 니까? 우 리 는 가장 큰 f [i - 1] [k] 값 을 직접 계산 할 수 있 습 니까? 이러한 서열 a [i] = b [j] 가 존재 한다 고 가정 하면 우 리 는 상태 전이 방정식 ② 를 계속 보면 b [j] > b [k], 즉 a [i] = b [j] 를 발견 할 수 있 습 니 다.되다
a [i] > b [k] 를 내 놓 으 면 이 표현 식 이 있 으 면 우 리 는 무엇 을 할 수 있 습 니까? 우 리 는 MAX 값 을 유지 하여 가장 큰 f [i - 1] [k] 값 을 저장 할 수 있 습 니 다. 즉, a [i] > a [j] 가 있 는 곳 만 있 으 면 최대 값 을 업데이트 할 수 있 습 니 다. 그래서 a [i] = b [j] 일 때 f [i] [j] = MAX + 1 이면 됩 니 다.
핵심 코드:
4. 567913. 사실 위의 코드 중 일 부 는 0 / 1 가방 과 비슷 하 다 는 것 을 알 수 있다. 즉, 매번 사용 하 는 것 은 위의 순환 에 사용 하 는 값, 즉 f [i - 1] [j] 이다. 그러면 우 리 는 0 / 1 가방 문 제 를 최적화 시 키 는 것 처럼 스크롤 배열 을 이용 하여 공간 을 최적화 할 수 있다.
핵심 코드:
4. 567913. 최 장 공공 하강 서브 시퀀스 를 구 하 는 것 이 라면? 분명 하 잖 아. 상태 정 의 를 바 꾸 자. 즉, f [i] [j] 는 a 꼬치 의 앞 i 개 정수 와 b 꼬치 의 앞 j 개 정수, 그리고 b [j] 를 마지막 으로 구 성 된 LCDS 의 길 이 를 나타 낸다. 구체 적 으로 실현 할 때 a [i] > b [j] 를 a [i] < b [j] 로 바 꾸 면 된다.
확장 읽 기:http://wenku.baidu.com/view/3e78f223aaea998fcc220ea0.html