Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 43
ANGKA SUBSEKUENS
Pak Dengklek memiliki array yang berisi N elemen, setiap elemen berada diantara 0 sampai 9 (inklusif). Pak Dengklek ingin mencari suatu subsekuens valid terpanjang dari array tersebut. Subsekuens dari suatu array adalah sekuens yang dapat diperoleh dengan menghapus beberapa elemen array tanpa mengubah urutan dari array tersebut. Sebagai contoh, array {1, 3, 3, 6, 7} memiliki subsekuens {1, 3, 6}, {1, 6, 7}, tetapi bukan {1, 7, 6} karena tidak mengubah urutan pada array asli.
Misalkan subsekuens yang dipilih adalah S. S disebut valid apabila dari 1 <= i < |S| (|S| adalah panjang dari array S), banyaknya i dimana Si != Si + 1 tidak lebih dari 1. Sebagai contoh subsekuens {1, 3, 3} valid karena dua angka berurutan yang nilainya beda tidak lebih dari satu, sedangkan subsekuens {1, 6, 7} tidak valid karena jumlah dua angka berurutan yang nilainya beda ada dua. Bantu Pak Dengklek menentukan panjang S valid yang terpanjang!
Batasan:
1 <= N <= 100.000
Format Masukan:
Baris pertama berisi sebuah bilangan N.
Baris kedua berisi N bilangan, masing-masing menandakan elemen ke-i dari array pak Dengklek.
Format Keluaran:
Sebuah bilangan seperti deskripsi diatas.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|
4 1 1 1 1 |
4 |
|
6 1 1 2 1 2 2 |
5 |
|
7 1 2 2 4 3 5 2 |
3 |
2 jawaban
Hocky Yudhiono7 tahun lalu
Cupu :(
0
Konsep pengerjaannya cukup sederhana, berbau prefix suffix dan greedy. Kita ingin mendapatkan array S yang valid, dengan susunan kurang lebih a,a,a,a,a,...,.,.,a,b.,.,.,.,.,.,b,b,b,b,b,
Intinya pasti ada suatu titik dimana subsq tersebut seperti itu, nah, untuk setiap titiknya, tinggal kita ambil saja maksimum di kiri dia elemen apa dan di kanan dia elemen apa
#include <bits/stdc++.h>
using namespace std;
int cnt[10]; //cnt[i] merupakan jumlah elemen i dari array
int isi[100005]; //isi[i] merupakan isi array
int pref[10][100005]; //pref[i][j] merupakan jumlah elemen i dari 1 hingga j
int ans,maxka,maxki,n; //maxka merupakan jumlah maksimum elemen di sebelah kanan pointer, maxki sebelah kiri.
int main(){
cin >> n;
for(int i = 1;i <= n;i++) cin >> isi[i]; //Membaca input
for(int i = 1;i <= n;i++){
cnt[isi[i]]++;
for(int j = 0;j <= 9;j++){
pref[j][i] = pref[j][i-1]; //Generate prefix
if(j == isi[i]) pref[j][i]++;
}
}
for(int i = 1;i <= n;i++){
maxka = maxki = 0; //Maximum dan minimum direset
for(int j = 0;j <= 9;j++){
maxki = max(maxki,pref[j][i]); //Di cek, elemen apa yang di sebelah kirinya paling banyak
maxka = max(maxka,cnt[j]-pref[j][i]); //Di cek, elemen apa yang di sebelah kanannya paling banyak
}
ans = max(ans,maxka+maxki); //Penggabungan dua elemen tersebut
}
cout << ans << endl; //Output jawaban
}
Noya Aldiputera7 tahun lalu
Jika ingin mendownvote, jangan lupa juga untuk komen tentang kesalahannya. That'll be helpful for everyone, don't let that be a habit.
Masuk untuk menulis jawaban
mantep nih O(n)