UVa 10131: Is Bigger Smarter?

동적 기획 문제.UVa103 Stacking Box와 유사하게 모두 제목이 끼워 넣는 방법을 판단하고 가장 긴 서열을 구한다.데이터 정렬을 앞당기면 약간의 시간 비용을 절약할 수 있다.
내 문제 해결 코드는 다음과 같습니다.
 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>



using namespace std;



#define MAXN 1005

int N;

int w[MAXN],s[MAXN];

int Rank[MAXN],Index[MAXN],NextInSeq[MAXN],LongLen[MAXN];

int cmp(const void *a, const void *b)

{

	int ai = *(int *)a, bi = *(int *)b;

	if(w[ai]!=w[bi]) return w[ai]-w[bi];

	return s[bi]-s[ai];

};

int dp(int n)

{

	if(LongLen[n]) return LongLen[n];

	int k = Index[n];

	for(int i=k+1; i<N; i++) if(w[n]<w[Rank[i]] && s[n]>s[Rank[i]]) if(LongLen[n]<dp(Rank[i]))

	{

		LongLen[n] = dp(Rank[i]);

		NextInSeq[n] = Rank[i];

	}

	return ++LongLen[n];

}

int main()

{

	N=0;

	while(scanf("%d %d",&w[N],&s[N])==2) N++;

	for(int i=0; i<N; i++) Rank[i] = i;

	qsort(Rank,N,sizeof(int),cmp);

	for(int i=0; i<N; i++) Index[Rank[i]] = i;

	memset(LongLen,0,sizeof(LongLen));



	int anslen = 0, ansi;

	for(int i=0; i<N; i++) if(anslen<dp(i)) { anslen = dp(i); ansi = i; }

	printf("%d
%d
",anslen,ansi+1);

	for(int i=1; i<anslen; i++) { ansi = NextInSeq[ansi]; printf("%d
",ansi+1); }

	return 0;

}