UVa 111: History Grading

這道題首先要對輸入進行處理，解題的一般思路是將所給的c數組與r數組按照各個歷史事件的rank重排，即最早的事件的編號放在數組的第一位......然後這題轉化為求兩個串的最長公共子序列長度的問題。

但我使用了另外一種解法（雖然仍然要用動態規劃 =-= ）：

只對輸入的c數組重排（即c數組中c[i]存放rank為i的事件的編號），r數組不變。建立ans數組，ans[i]存放以rank為i為結尾的最長序列長度，初始化均為1。

程序從第0個開始填充ans數組。當執行到求ans[i]時，分別判斷rank從0 — i-1 的事件，如j事件，在學生的解答（即r數組中數據）中發生時間是否也在i事件之前，如果在其之前，則用ans[j]+1更新ans[i]（因為ans[i]初始化為1）。ans數組填充完畢後，其中最大值即為所求結果。

我的代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;

int c[20],r[20];
int ans[20];
int N;
int main()
{
	cin >> N;
	int ci;
	for(int i=0; i<N; i++)
	{//按時間順序重排c數組
		cin >> ci;
		c[ci-1]=i;
	}
	int tmp;
	while(cin >> tmp)
	{
		r[0]=tmp;
		ans[tmp]=0;
		for(int i=1; i<N; i++)
			cin >> r[i];

		int maxlen=1;
		ans[0]=1;		
		for(int i=1; i<N; i++)
		{
			ans[i]=1;
			//依次判斷事件0~i-1
			for(int j=0; j<i; j++)
			{
				if(r[c[j]] < r[c[i]]) { if(ans[i]<(ans[j]+1)) ans[i]=ans[j]+1; }
			}
			if(maxlen<ans[i]) maxlen=ans[i];
		}
		cout << maxlen << endl;
	}
	return 0;
}