UVa-111 : History Grading

問題概要

LIS。N<20。

解法

練習のつもりでO(N*log N)解を書く。入力の変換が最も面倒。

acceptされたコード

計算量O(N * log N)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 20;
const int INF = 1<<29;

int N;
int correct[MAX_N], value[MAX_N];
int rank[MAX_N], as[MAX_N];
int dp[MAX_N];

void init(){
	scanf("%d", &N);
	for(int i=0, x; i<N; i++){
		scanf("%d", &x);
		correct[x-1] = i;
	}

	for(int i=0; i<N; i++){
		value[correct[i]] = i;
	}

}

bool init2(){
	bool ok = false;
	for(int i=0; i<N; i++){
		ok = scanf("%d", rank + i) != EOF;
	}

	if(!ok){
		return false;
	}

	for(int i=0; i<N; i++){
		as[rank[i] - 1] = i;
	}

	for(int i=0; i<N; i++){
		as[i] = value[as[i]];
	}

	return true;
}

int solve(){
	fill(dp, dp + N, INF);
	for(int i=0; i<N; i++){
		*lower_bound(dp, dp + N, as[i]) = as[i];
	}

	int ans = 0;
	for(int i=0; i<N; i++)if(dp[i] < INF){
		ans = i + 1;
	}

	return ans;
}

int main(){
	init();
	while(init2()){
		printf("%d\n", solve());
	}

	return 0;
}