hdu 1025 Constructing Roads In JGShining's Kingdom

2 차원 DP 시간 초과...
클릭 하여 링크 열기
하나의 서열 d [1. 9] = 2153, 6489, 7 이 존재 한다 고 가정 하면 LIS 길이 가 5 인 것 을 알 수 있다.
다음 단 계 는 그것 을 찾 아 보 자.
우 리 는 하나의 서열 B 를 정의 한 후에 i = 1 to 9 로 하여 금 이 서열 을 하나씩 고찰 하 게 한다.
그 밖 에 우 리 는 하나의 변수 인 Len 으로 현재 최 장 계산 이 얼마 인지 기록 했다.
먼저, d [1] 을 B 에 질서 있 게 넣 고 B [1] = 2, 즉 1 개의 숫자 2 만 있 을 때 길이 가 1 인 LIS 의 최소 끝 은 2 라 는 것 이다.이때 Len = 1
그리고 d [2] 를 B 에 질서정연 하 게 넣 어 B [1] = 1, 즉 길이 가 1 인 LIS 의 최소 끝 은 1, d [1] = 2 가 소 용이 없다 는 것 을 쉽게 이해 할 수 있 습 니 다.이때 Len = 1
이 어 d [3] = 5, d [3] > B [1], 그래서 B [1 + 1] = B [2] = d [3] = 5 는 길이 가 2 인 LIS 의 최소 끝 이 5 라 는 뜻 으로 이해 하기 쉽 죠.이때 B [1. 2] = 1, 5, Len = 2
다시, d [4] = 3, 그것 은 1, 5 사이 에 딱 붙 었 다. 1 의 위치 에 놓 는 것 은 분명 적합 하지 않다. 1 이 3 보다 적 고 길이 가 1 인 LIS 의 최소 끝 은 1 이 어야 하기 때문에 길이 가 2 인 LIS 의 최소 끝 은 3 이 므 로 5 를 탈락 시 킬 수 있다. 이때 B [1. 2] = 1, 3, Len = 2
계속, d [5] = 6, 그것 은 3 뒤에 있 습 니 다. B [2] = 3, 6 은 3 뒤에 있 기 때문에 B [3] = 6 을 쉽게 알 수 있 습 니 다. 이때 B [1. 3] = 1, 3, 6 은 쉽게 이해 할 수 있 죠?렌 = 3 이다.
여섯 번 째, d [6] = 4, 그것 이 3 과 6 사이 에 있 는 것 을 보 세 요. 그래서 우 리 는 6 을 교체 해서 B [3] = 4 를 얻 을 수 있 습 니 다.B [1. 3] = 1, 3, 4, Len 계속 3
일곱 번 째, d [7] = 8, 그것 은 매우 크 고 4 보다 크다, 응.그래서 B [4] = 8.렌 이 4 가 됐어.
여덟 번 째, d [8] = 9, B [5] = 9, 응.렌 은 5 까지 계속 커 졌 다.
마지막, d [9] = 7, 그것 은 B [3] = 4 와 B [4] = 8 사이 에 있 기 때문에 우 리 는 최신 B [4] = 7, B [1. 5] = 1, 3, 4, 7, 9, Len = 5 를 알 고 있다.
그래서 우 리 는 LIS 의 길이 가 5 라 는 것 을 알 게 되 었 다.
!!!!! 주의이 1, 3, 4, 7, 9 는 LIS 가 아니 라 해당 길이 의 LIS 의 최소 끝 에 저 장 됩 니 다.이 끝 이 있 으 면 우 리 는 하나하나 데 이 터 를 삽입 할 수 있다.마지막 d [9] = 7 을 업데이트 하 는 것 은 이 그룹의 데이터 에 아무런 의미 가 없 지만 뒤에 두 개의 숫자 8 과 9 가 더 나 오 면 8 을 d [5], 9 를 d [6] 로 업데이트 하여 LIS 의 길 이 를 6 으로 얻 을 수 있다.
그리고 한 가 지 를 발견 해 야 합 니 다. B 에 데 이 터 를 삽입 하 는 것 은 질서 가 있 고 바 꾸 는 것 입 니 다. 이동 할 필요 가 없습니다. 즉, 우 리 는 2 분 으로 찾 을 수 있 습 니 다. 모든 숫자의 삽입 시간 을 O (logN) ~ ~ ~ ~ ~ 로 최적화 시 켜 알고리즘 의 시간 복잡 도 를 O (NLogN) 로 낮 출 수 있 습 니 다 ~

#include"stdio.h"
int num[500011];
int ans[500011];
int main()
{
	int n,k=1;
	int len,low,up,mid;
	int i;
	int temp1,temp2;
	while(scanf("%d",&n)!=-1)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&temp1,&temp2);
			num[temp1]=temp2;
		}
		ans[1]=num[1];
		len=1;
		for(i=2;i<=n;i++)
		{ //  ， 。。- -
			low=1;
			up=len;
			while(low<=up)
			{
				mid=(low+up)/2;
				if(ans[mid]<num[i]) low=mid+1;
				else up=mid-1;
			}
			ans[low]=num[i];
			if(low>len) len++;
		}
		printf("Case %d:
",k);
		if(len==1)	printf("My king, at most 1 road can be built.");
		else	printf("My king, at most %d roads can be built.",len);
		printf("
");
		printf("
");
		k++;
	}
	return 0;
}