동적 프로그래밍 솔루션 - 해결 방법? (올바른 방향으로 나를 가리 키십시오)

Question

나는 USACO의 동적 프로그래밍에 대한 질문이 있습니다. (컴퓨터 과학 학습).

질문 텍스트는 여기에 있습니다 : http://pastebin.com/MiJ5aEWc

나는이 최대 Inc의 서브 시퀀스 유사 수 있습니다 생각하지만, 누군가가 올바른 방향으로 날 지점 수 있습니까?

감사합니다.

Answer 1

예. O (n log n), 동적 프로그래밍 :
먼저 소를 x 좌표로 정렬하고 번식 유형을 정수 [1..k]로 매핑하십시오. (k < = n) : O (n log n)
dp [i] = j 번째 젖소부터 i 번째 돌까지 모든 번식이 나타나도록하는 최대 색인 j 또는 존재하지 않는 경우 -1.
각 k에 대해 dp [i] 암소 범위 [k, i]가 허용되고 i <j -> dp [i] < = dp [j]이므로 녹음을 통해 O (n)의 dp 부분을 풀 수 있습니다. 젖소 범위 [dp [i], i]에있는 각 유형의 소의 수.