a676 - 00111 - History Grading
題目描述
題目要求計算學生歷史事件排序答案與標準答案之間的最長遞增子序列的長度，作為學生的得分。標準答案代表事件發生的正確順序，學生的答案則是一個事件順序的排列。得分計算基於學生答案中，事件順序與標準答案相對順序一致的最長序列的長度。
解題思路
本題的核心是找到學生答案中最長遞增子序列的長度，其中“遞增”的定義是事件在標準答案中的相對順序。程式首先讀取標準答案。然後，對於每個學生的答案，程式會建立一個 l 陣列來儲存每個位置的最長遞增子序列的長度。tmp 陣列用於儲存學生答案中每個事件在標準答案中的位置。程式使用兩層迴圈比較學生的答案和標準答案，並更新 l 陣列。最後，程式找到 l 陣列中的最大值，即最長遞增子序列的長度，並將其作為學生的得分輸出。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是事件的數量。這是因為程式使用了兩層迴圈來計算最長遞增子序列。
- 空間複雜度: O(n)，程式使用了
ans、l和tmp三個大小為 n 的陣列。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
cin >> n;
int ans[n]={0},t,tmp[n];
for(int i=0;i<n;++i){
cin >> t;
ans[i]=t;
}
while(cin >> t){
int l[n]={1},sc=0;
tmp[t-1]=1;
for(int i=1;i<n;++i){
l[i]=1;
cin >> t;
tmp[t-1]=i+1;
}
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(ans[tmp[i]-1]<ans[tmp[j]-1])
l[j]=max(l[i]+1,l[j]);
for(int i=0;i<n;++i)
if(l[i]>sc)
sc=l[i];
cout << sc << "\n";
}
}