本文主要是介绍uva111 - History Grading（历史考试），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题目前知道两个思路，（最大上升序列）和（最长公共自序列）
我首先想到的是最大上升序列。但是由于思路不清楚，代码没能立即写出来
思路：
读取并存储第一个字符串，这个字符串交代了每个事件发生的时序，如a[4] = 1表示事件4在第1个时间发生了、
接写来就是读取需要处理的字符串了。每个字符串表示事件事实发生的时序数列，
我们先把b转化成事件发生顺序，即把每个时序发生的放到对应位置上
然后再把每个时间换成a中对应的时序，求最大上升序列。
如果是1，2，3……就说明时序完全正确
代码如下：
#include <cstdio>
int n, s[25], a[25], f[25];
int solve()
{int ans, max = 0;for(int i = n; i >= 1; i--){ans = 0;for(int j = i+1; j <= n; j++){if(a[i]<a[j]) ans = ans<f[j]?f[j]:ans;}f[i] = ans+1;max = max<f[i]?f[i]:max;}return max;
}
int main ()
{int tt;scanf("%d",&n);for(int i = 1; i <= n; i++) { scanf("%d",&tt); s[i] = tt; }while(1){for(int i = 1; i <= n; i++) {if(scanf("%d",&tt)==EOF) return 0; a[tt] = s[i];}//for(int i = 1; i <= n; i++) printf("%d ",a[i]);printf("\n");printf("%d\n",solve());}return 0;
}
思路：
用m，n表示a，b串的位置
用f[m][n]表示a串前m个字符组成的子串和b串前n子串比较得到的最长子序列的长度
我们只需按照以下规则来走就好了
1：if(a[m]==a[n]) f[m][n] = f[m-1][n-1]+1;
2：else f[m][n] = max(f[m][n-1],f[m-1][n]);
代码如下：
#include <cstdio>
#include <cstring>
#define max(a,b) a>b?a:b
int n, b[25], a[25], f[25][25];
int solve()
{memset(f,0,sizeof(f));int ans, max = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(a[i]==b[j]) f[i][j] = f[i-1][j-1]+1;else f[i][j] = max(f[i][j-1],f[i-1][j]);}}return f[n][n];
}
int main ()
{int tt;scanf("%d",&n);for(int i = 1; i <= n; i++) { scanf("%d",&tt); a[tt] = i; }while(1){for(int i = 1; i <= n; i++) {if(scanf("%d",&tt)==EOF) return 0; b[tt] = i;}printf("%d\n",solve());}return 0;
}
这篇关于uva111 - History Grading（历史考试）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
