a559 - NCPC PC Matrix
題目描述
題目給定 m 個集合，每個集合包含 n 個整數。目標是找到可以形成兼容矩陣的最大集合數量 k_max。兼容矩陣需要滿足以下條件：每一行來自不同的集合，並且是該集合的排列；對於所有 i 和 j，b_i,j < b_{i+1},j，其中 b_i,j 是矩陣的第 i 行第 j 列的元素。
解題思路
解題思路是先對每個集合中的元素進行排序。然後，使用貪心策略和動態規劃的思想來找到最大的兼容集合數量。
- 對每個集合進行排序，以便更容易比較元素的大小。
- 使用
length陣列來儲存以每個集合為結尾的最長兼容集合的長度。 - 遍歷所有集合，對於每個集合，檢查它是否可以附加到之前的集合上，如果可以，則更新
length陣列。 - 最後，找到
length陣列中的最大值，即為 k_max。cmp2函式用於判斷兩個集合是否滿足兼容條件，即第一個集合的所有元素都小於第二個集合的所有元素。
複雜度分析
- 時間複雜度: O(m * n * log n + m^2)
- 排序每個集合需要 O(n * log n) 的時間，總共 m 個集合，所以是 O(m * n * log n)。
- 尋找最長兼容集合需要 O(m^2) 的時間。
- 因此，總時間複雜度為 O(m * n * log n + m^2)。
- 空間複雜度: O(m * n)
- 需要儲存 m 個集合，每個集合包含 n 個整數，所以空間複雜度為 O(m * n)。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct arr{
int an[21];
};
arr ans[2501];
int n,length[2501],m,t;
bool cmp(arr x,arr y){
for(int i=0;i<n;++i){
if(x.an[i]<y.an[i]){return 1;}
else if(x.an[i]>y.an[i]){return 0;}
}
return 0;
}
bool cmp2(arr x, arr y){
for(int i=0;i<n;++i)
if(x.an[i]<=y.an[i])return 0;
return 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> m >> n;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j)
cin >> ans[i].an[j];
sort(ans[i].an,ans[i].an+n);
}
sort(ans,ans+m,cmp);
for (int i=0; i<m; i++) length[i] = 1;
for (int i=0; i<m; i++)
for (int j=0; j<i; j++)
if (ans[i].an[n-1]<ans[j].an[0]||cmp2(ans[i],ans[j]))
length[i] = max(length[i], length[j] + 1);
int l = 0;
for (int i=0; i<m; i++)
l = max(l, length[i]);
cout << l << "\n";
}
}