Codevs 5288 항로 설계(동적 기획 강화판) 문제풀이 보고서

[문제 설명]
  
한 나라는 강에 의해 남북 두 부분으로 나누어졌는데 남쪽 해안과 북쪽 해안에는 모두 N대 도시가 있고 각 도시는 맞은편 해안에 유일한 우호 도시가 있다.두 도시 모두 같은 우호 도시는 없다.모든 우호 도시는 항로가 왕래하기를 희망한다.그래서 그들은 정부에 신청을 했다.강에 일년 내내 안개가 끼기 때문이다.정부는 두 노선이 교차하는 것을 허락하지 않기로 결정했다.
너의 임무는 정부 관리들이 교차하는 항로가 가장 많이 생기지 않도록 어떤 항로를 건설해야 하는지를 결정하도록 절차를 쓰는 것이다. 
 
    
[형식 입력]
  
첫 번째 줄의 정수 N은 강 양안에 분포하는 도시의 대수를 나타낸다.다음 N행은 줄마다 두 개의 빈칸으로 구분된 정수 C, D(C, D<=10^9)로 각 우호도시가 강기슭과 서변경선을 따라 거리를 나타낸다. C는 북안도시의 거리를 나타내고 D는 남안도시의 거리를 나타낸다. 강과 같은 쪽에서 두 도시의 위치는 모두 다르다.
 
    
[출력 형식]
   
안전 조건 하에서 개통할 수 있는 최대 항로 수.
 
    
[샘플 입력]
   
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
 
    
[샘플 내보내기]
   
4
 
    
[데이터 범위]
   
　　1<=N<=500000
문제풀이 사고방식: 문제에 따라 우호도시가 안전조건에서 개통할 수 있는 최대 항로 수를 직접 계산하면 어떤 항로가 교차하는지 알 수 없기 때문에 먼저 항로를 북안도시에서 국경선까지의 거리에 따라 작은 항로에서 큰 항로로 정렬할 수 있다. 정렬 후 각 항로에 대응하는 남안도시에서 국경선까지의 거리도 작은 항로에서 큰 항로로 점차 증가해야만 항로가 교차하지 않는다는 것을 보장할 수 있다(즉 안전조건을 충족시키는 것).
그래서 이 문제는 순서를 정한 후에 최대 단일 증자 서열을 구하는 문제로 바뀌었다. 가장 간단한 생각은 동적 기획이다. 상태 함수 f(i)를 설정하면 전 i가 우호 도시에 대해 표시하고 i가 우호 도시에 대해 끝을 맺을 때 안전 조건에서 개통할 수 있는 최대 항로 수는 상태 이동 방정식을 f(i)=max{f(j)|1<=j
조건을 충족시키는 가장 큰 f(j)를 찾는 데 많은 시간이 걸렸기 때문에 조건을 충족시키는 가장 큰 f(j)를 직접 찾을 수 있었으면 좋겠다. 그래서 수조를 활용할 수 있다고 생각했다. 수조 g[i]는 길이가 i인 상승자 서열의 마지막 원소의 최소값을 나타낸다. g[i]는 계산 과정에서 항상 단조롭게 증가하기 때문이다(서로 인접할 수 있는 두 값이 같을 수도 있다).따라서 f(i)에 대응하는 제i가 우호도시 중남안도시에서 국경선까지의 거리를 알면 이분찾기(lower bound)를 이용하여 첫 번째 거리가 첫 번째 상승자 서열의 길이보다 크다는 것을 찾을 수 있다. 구한 값은 f(i)의 값(실제적으로 구한 값을 먼저 1로 줄이고 1을 더하는 것)이다.f(i)를 계산하는 동시에 g[i]의 값을 업데이트하는 데 주의해야 한다. 만약에 찾을 때 제i가 우호도시 중 남안도시에서 국경선까지의 거리가 가장 크거나 이때 g[f(i)]의 값이 a[i]보다 크다면.d가 크면 g[f(i)]=a[i].d, 또한 이분 검색을 사용하려면 g수조의 길이를 기록해야 한다. 만약에 검색할 때 제i가 우호도시 중남안도시에서 국경선까지의 거리가 가장 크고 g수조의 길이는 1을 추가해야 한다.주의해야 할 것은 프로그램을 작성할 때 f(i)는 생략할 수 있다는 것을 발견하고 매번 g수 그룹을 업데이트할 때마다 g수 그룹의 길이가 답이다.이런 방법의 시간 복잡도는 O(N*log2N)이다.

#include
#include
#include
#include
#include
using namespace std;
const int maxn=500005;
int N;
struct data
{
	int c,d;
};
data a[maxn];
bool cmp(data aa,data bb)
{
	return aa.ccnt || g[t]>a[i].d)  g[t]=a[i].d;  //  g[i]
		if(t>cnt)  cnt=t;  //  g    
	}
	printf("%d
",cnt);
}
int main()
{
	//freopen("48.in","r",stdin);
	//freopen("48.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	scanf("%d%d",&a[i].c,&a[i].d);  //                       
	sort(a+1,a+1+N,cmp);
	solve();
	return 0;
}