Paste: UVA_111HistoryGrading

Author: XO
Mode: c++
Date: Mon, 23 Sep 2013 11:32:04
Plain Text |
#include <iostream>
#include <cstring>
#define MAXN 20

int src[MAXN];
int answer[MAXN];
int length;

int rankTable[MAXN];

int apos_lessthan_bpos(int a,int b)
{
	for (int i = 0; i<length; ++i)
	{
		if (src[i] == a){
			return 1;
		}
		if (src[i] == b){
			return 0;
		}
	}
}

int rank(int index)
{
	if (0 != rankTable[index]){
		return rankTable[index];
	}
	int maxRank = 1;
	for (int i = index + 1;i<length; ++i)
	{
		if (apos_lessthan_bpos(answer[index],answer[i])){
			int subRank = rank(i) + 1;
			maxRank = maxRank>subRank?maxRank:subRank;
		}
	}
	rankTable[index] = maxRank;
	return maxRank;
}

int main()
{
	std::cin >> length;
	int level;
	for (int i = 0; i < length; ++i)
	{
		std::cin >> level;
		--level;
		*(src + level) = i;
	}

	while (!std::cin.eof())
	{
		memset(rankTable,0,sizeof(int)*length);
		for (int i = 0; i < length; ++i)
		{
			std::cin >> level;
			--level;
			*(answer + level) = i;
		}
		int maxRank = 0,subRank = 0;
		for (int i = 0; i < length; ++i)
		{
			subRank = rank(i);
			maxRank = maxRank<subRank?subRank:maxRank;
		}

		std::cout << maxRank << std::endl;
	}

	return 0;

}

New Annotation

Summary:
Author:
Mode:
Body: