UVa 111 History Grading

题目描述

本题源于历史考试评分问题。学生需要将若干历史事件按时间顺序排序。完全正确的排序得满分，但对于部分排序错误的情况，需要给予部分分数。题目要求采用第二种评分方式：
计算学生答案中最长的相对顺序正确的子序列的长度（子序列不必连续，但需保持事件间的相对顺序与正确答案一致）。

输入包含多组测试数据。第一行为事件数n nn（2 ≤ n ≤ 20 2 \leq n \leq 202≤n≤20）。第二行给出n nn个整数，表示正确答案的事件排序（注意这里是排名顺序，表示事件i ii的正确排名为c i c_ici​）。随后每行是学生的答案，格式同正确答案。

输出每个学生答案的得分，即最长符合相对顺序的子序列长度。

注意：题目中涉及两个关键概念：

• 顺序（Ordering \texttt{Ordering}Ordering）：事件按时间排列的顺序。
• 排名（Ranking \texttt{Ranking}Ranking）：事件在顺序中的位置（第几位）。

例如，正确答案为1 2 3 4，学生答案为1 3 2 4，则最长符合的子序列为1 2 4或1 3 4，长度为3 33。

解题思路

问题的本质是求最长公共子序列（LCS \texttt{LCS}LCS），但经过转换可变为求最长上升子序列（LIS \texttt{LIS}LIS），从而降低复杂度。

关键转换

设正确答案的顺序为c 1 , c 2 , . . . , c n c_1, c_2, ..., c_nc1​,c2​,...,cn​（c i c_ici​表示事件i ii的正确排名）。学生给出的排名序列为r 1 , r 2 , . . . , r n r_1, r_2, ..., r_nr1​,r2​,...,rn​（r i r_iri​表示学生给事件i ii的排名）。

我们要找的是学生序列中相对顺序与正确答案一致的子序列。
如果我们将正确答案看作一个从事件到其正确排名的映射（即“事件i ii的正确排名为c i c_ici​”），那么学生答案中的每个事件i ii对应的正确排名就是c i c_ici​。
若学生答案中事件i ii出现在第p o s pospos位，则其正确排名为c i c_ici​。
我们想找学生序列中一个子序列，使得这些事件的正确排名是递增的。
因此，我们将学生答案的每个位置转换为其事件的正确排名，然后在该转换后的序列中求最长上升子序列（LIS \texttt{LIS}LIS）的长度，即为所求得分。

算法步骤

1. 读入正确答案，建立数组o r d e r orderorder，使得o r d e r [ r a n k ] = e v e n t order[rank] = eventorder[rank]=event，即排名r a n k rankrank对应的事件编号。
2. 对每个学生答案：
   • 将学生答案中每个位置i ii的事件编号转换为该事件的正确排名，得到新序列e v e n t s eventsevents。
   • 在e v e n t s eventsevents序列上计算最长上升子序列的长度。
3. 输出每个学生答案的LIS \texttt{LIS}LIS长度。

时间复杂度

事件数n ≤ 20 n \leq 20n≤20，直接O ( n 2 ) O(n^2)O(n2)的LIS \texttt{LIS}LIS算法完全可行。也可使用O ( n log ⁡ n ) O(n \log n)O(nlogn)的优化算法。

参考代码

以下是三种实现，它们核心思路相同，但在数据结构和LIS \texttt{LIS}LIS实现细节上略有差异。

实现一：

此版本使用数组存储，LIS \texttt{LIS}LIS采用O ( n 2 ) O(n^2)O(n2)的DP \texttt{DP}DP方法。

• 数组order[rank] = event存储正确顺序。
• getIndex函数用于根据事件编号查找其正确排名。
• lis函数用动态规划计算最长上升子序列。

// History Grading// UVa ID: 111// Verdict: Accepted// Submission Date: 2011-11-25// UVa Run Time: 0.052s//// 版权所有（C）2011，邱秋。metaphysis # yeah dot net//// [解题方法]// 可以将问题转化为求最长上升子序列的问题。#include<bits/stdc++.h>usingnamespacestd;#defineMAXN25intorder[MAXN],events[MAXN],length[MAXN],n;intlis(void){for(inti=1;i<=n;i++)length[i]=1;for(inti=1;i<=n;i++)for(intj=1;j<i;j++)if(events[j]<events[i]&&(length[j]+1)>length[i])length[i]=length[j]+1;intmaxLength=1;for(inti=1;i<=n;i++)maxLength=max(maxLength,length[i]);returnmaxLength;}intgetIndex(intindex){for(inti=1;i<=n;i++)if(order[i]==index)returni;}intmain(intargc,char*argv[]){string line;intindex;cin>>n;for(inti=1;i<=n;i++){cin>>index;order[index]=i;}cin.ignore(1024,'\n');while(getline(cin,line)){istringstreamiss(line);for(inti=1;i<=n;i++){iss>>index;events[index]=getIndex(i);}cout<<lis()<<endl;}return0;}

实现二：

与实现一类似，但使用STL \texttt{STL}STL的find函数替代getIndex，代码更简洁。

// History Grading// UVa ID: 111// Verdict: Accepted// Submission Date: 2016-02-29// UVa Run Time: 0.003s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=25;intorder[MAXN],events[MAXN],length[MAXN],n;intlis(){for(inti=1;i<=n;i++)length[i]=1;for(inti=1;i<=n;i++)for(intj=1;j<i;j++)if(events[j]<events[i]&&(length[j]+1)>length[i])length[i]=length[j]+1;intmaxLength=1;for(inti=1;i<=n;i++)maxLength=max(maxLength,length[i]);returnmaxLength;}intmain(intargc,char*argv[]){string line;intindex;order[0]=0;cin>>n;for(inti=1;i<=n;i++){cin>>index;order[index]=i;}cin.ignore(1024,'\n');while(getline(cin,line)){istringstreamiss(line);for(inti=1;i<=n;i++){iss>>index;events[index]=find(order,order+n,i)-order;}cout<<lis()<<endl;}return0;}

实现三

此版本使用O ( n log ⁡ n ) O(n \log n)O(nlogn)的LIS \texttt{LIS}LIS算法，并采用vector存储数据，代码更现代化。

// History Grading// UVa ID: 111// Verdict: Accepted// Submission Date: 2016-05-10// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<int>order,events;intlis(){vector<int>M;M.push_back(events.front());for(autoit=events.begin()+1;it!=events.end();it++)if(*it>M.back())M.push_back(*it);else{autolocation=upper_bound(M.begin(),M.end(),*it);*location=*it;}returnM.size();}intmain(intargc,char*argv[]){intn,index;string line;cin>>n;order.resize(n);events.resize(n);for(inti=1;i<=n;i++){cin>>index;order[index-1]=i;}cin.ignore(1024,'\n');while(getline(cin,line)){istringstreamiss(line);for(inti=1;i<=n;i++){iss>>index;events[index-1]=find(order.begin(),order.end(),i)-order.begin();}cout<<lis()<<'\n';}return0;}

总结

本题的关键在于理解“相对顺序正确”等价于“正确排名递增”，从而将问题转化为LIS \texttt{LIS}LIS问题。三种实现方法核心相同，差异主要在于：

• 实现一和实现二使用O ( n 2 ) O(n^2)O(n2)的DP \texttt{DP}DP计算LIS \texttt{LIS}LIS，代码清晰易懂。
• 实现三使用O ( n log ⁡ n ) O(n \log n)O(nlogn)的贪心+二分优化，效率更高，且使用STL \texttt{STL}STL容器和算法，代码更简洁。