e588 - 12385 - Interesting Sequences
題目描述
題目要求找出一個整數序列中，互不衝突的 "interesting" 子序列的最大數量。"interesting" 子序列是指首尾元素相同的子序列，而互不衝突的子序列是指它們之間沒有重疊。
解題思路
本題採用貪心策略。首先，使用一個陣列 c 記錄每個數字最後出現的位置。然後，遍歷輸入序列，統計每個位置的元素作為 "interesting" 子序列結尾的次數，儲存在 ma 陣列中。接著，從序列的開頭開始，每次選擇最靠右邊的、且有元素作為結尾的 "interesting" 子序列，並將其包含的元素從 ma 陣列中移除。重複此過程，直到遍歷完整個序列。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int a[100005][2],ma[100005],c[100005],n,t;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n;
for(int i=0;i<=100000;++i){
c[i]=n;
a[i][1]=n;
ma[i]=0;
}
int it=0,ans=0;
for(int i=0;i<n;++i){
cin >> a[i][0];
if(c[a[i][0]]!=n){
a[c[a[i][0]]][1]=i;
}
c[a[i][0]]=i;
}
for(int i=0;i<n;++i){
ma[a[i][1]]++;
}
int tmp=0;
while(it<n){
for(int i=it;i<=n;++i){
if(ma[i]){
tmp=i;
break;
}
}
if(tmp<n){
++ans;
for(int i=it;i<tmp;++i){
ma[a[i][1]]--;
}
}
it=tmp;
}
cout << ans << "\n";
}
}