本文主要是介绍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-1for(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;
}
这篇关于UVa 111: History Grading的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
