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; }