题目描述
在信息科学中有一些是关于在某些条件限制下,找出一些计算的最大值。 以历史考试来说好了,学生被要求对一些历史事件根据其发生的年代顺序来排列。所有事件顺序都正确的学生无疑的可以得满分。但是那些没有全对的人又该如何给分呢?以下有2种可能的给分方式: 1. 每个与标准答案的顺序相同的事件得1分 2. 每个在最长(但不一定要连续)的序列事件中,其相对的顺序亦可以在标准答案发现者,每个事件得1分。 举例说明:如果有4个事件其发生时间的顺序依次是1 2 3 4(就是标准答案啦,意思是第1个事件发生顺序为1,第2个事件发生的顺序为2,......)。所以如果学生回答此4个事件发生的顺序依次是1 3 2 4的话,根据上面第1种方法可以得2分(第1个及第4个事件)。但是如果以上面第2种方法可以得3分(1 2 4或者1 3 4其相对的顺序可以在标准答案发现) 在本问题中,请你写一个程序以第2个方法算出学生该得多少分。
Input
只考一次试,所以输入的第1列有一个整数n(2 <= n <= 20)代表此次历史考试有多少个事件要排序。第2列为标准答案,有n个正整数c1,c2,......cn,(其内容为1到n的某种排列),c1代表第1个事件发生的顺序,c2代表第2个事件发生的顺序,依此类推。 从第3列开始每列为一学生的答案,每列有n个正整数r1,r2,......rn,(其内容亦为1到n的某种排列),r1代表学生回答第1个事件发生的顺序,r2代表学生回答第2个事件发生的顺序,依此类推。
Output
对每一学生的答案,输出其所得的分数。
Sample Input
103 1 2 4 9 5 10 6 8 71 2 3 4 5 6 7 8 9 104 7 2 3 10 6 9 1 5 83 1 2 4 9 5 10 6 8 72 10 1 3 8 4 9 5 7 6
Sample Output
65109
由于是求事件的最长公共子序列,而输入的是时间,所以要处理下
1 #include
2 #include
3 #include
4 using namespace std;
5
6 const int MAXN = 25;
7
8 int dp[MAXN][MAXN];
9
10 int main()
11 {
12
13 int n;
14 int c[MAXN];
15 int r[MAXN];
16 int i, j;
17 int t;
18
19 while (~scanf("%d", &n)) {
20 for (i = 1; i <= n; ++i) {
21 scanf("%d", &t);
22 c[t] = i;
23 }
24 while (~scanf("%d", &t)) {
25 r[t] = 1;
26 for (i = 2; i <= n; ++i) {
27 scanf("%d", &t);
28 r[t] = i;
29 }
30 memset(dp, 0, sizeof(dp));
31 for (i = 1; i <= n; ++i) {
32 for (j = 1; j <= n; ++j) {
33 if (c[i] == r[j]) {
34 dp[i][j] = dp[i - 1][j - 1] + 1;
35 } else {
36 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
37 }
38 }
39 }
40 printf("%d\n", dp[n][n]);
41 }
42 }
43
44 return 0;
45 }
好像可以转化为求最长上升子序列来做,
http://www.cnblogs.com/jusonalien/p/4060871.html
好文链接
发表评论