Mini-proyek Bagian 3: Satu Soal Tiga Pendekatan

Proyek ini mengambil satu soal dan menyelesaikannya tiga kali: dengan brute force (Bab 11), dengan greedy (Bab 12), dan dengan dynamic programming (Bab 13). Tujuannya melihat langsung perbedaan ketiganya — dalam kecepatan dan dalam kebenaran.

Soalnya

Memetik mangga. Di sepanjang pagar berjajar n pohon mangga. Pohon ke-i berbuah a[i] mangga. Pak Dengklek boleh memetik dari pohon mana saja, tetapi tidak boleh dari dua pohon yang bersebelahan (nanti ketahuan). Berapa mangga terbanyak yang bisa ia petik?

Masukan. Baris pertama n. Baris kedua n bilangan bulat a[1..n].

Keluaran. Satu bilangan: jumlah mangga terbanyak.

Batasan. Subsoal 1 (30 poin): n ≤ 20. Subsoal 2 (30 poin): n ≤ 5.000. Subsoal 3 (40 poin): n ≤ 1.000.000. Semua 0 ≤ a[i] ≤ 10⁹.

Contoh masukan:

6
5 1 8 2 9 3

Contoh keluaran:

22

Penjelasan: petik pohon 1, 3, dan 5 → 5 + 8 + 9 = 22.

Yang harus dibuat

Tiga fungsi di dalam satu berkas, ditambah pengukuran dan perbandingan.

  1. brute(n) — telusuri semua 2ⁿ cara memilih pohon, buang yang bersebelahan, ambil jumlah terbesar. Hanya dipakai untuk n ≤ 20.
  2. greedy(n) — berulang kali ambil pohon berbuah terbanyak yang masih boleh dipetik, lalu tandai kedua tetangganya sebagai terlarang. Pendekatan ini salah. Tugasmu menemukan contoh kasus yang membuktikannya.
  3. dp(n) — dynamic programming, O(n).

Lalu, di main:

  • Baca masukan, cetak jawaban versi dp (inilah jawaban yang dikirim ke penilai).
  • Tambahkan bagian penguji: bangkitkan array acak berukuran n ≤ 12, bandingkan ketiganya, dan cetak contoh kasus pertama yang membuat greedy berbeda dari brute.
  • Ukur waktu brute dan dp untuk n = 22, lalu waktu dp untuk n = 1.000.000.

Petunjuk DP

Jawab lima pertanyaan dari Bab 13 sebelum menulis kode:

  1. Keadaan. dp[i] = mangga terbanyak bila hanya mempertimbangkan i pohon pertama.
  2. Kasus dasar. dp[0] = 0, dp[1] = a[1].
  3. Transisi. Untuk pohon ke-i ada dua pilihan — tidak dipetik (dp[i-1]) atau dipetik (dp[i-2] + a[i]). Ambil yang lebih besar.
  4. Urutan. Dari kecil ke besar.
  5. Jawaban. dp[n].

Petunjuk lain

  • Jumlah mangga bisa mencapai 10⁶ × 10⁹ = 10¹⁵. Pakai long long.
  • Untuk n = 1.000.000, array harus global.
  • brute dengan n = 22 menelusuri 4 juta himpunan bagian. Kalau pemeriksaan "ada dua bit bersebelahan" dilakukan lebih dulu (mask & (mask >> 1)), sebagian besar langsung dibuang dan waktunya masih di bawah sepersepuluh detik. Naikkan ke n = 30 dan rasakan bedanya: jumlah mask menjadi 256 kali lipat.

Yang harus dilaporkan

Tulis sebagai komentar di bagian atas berkasmu:

  • contoh kasus terkecil yang membuat greedy salah, beserta kedua jawabannya;
  • waktu brute dan dp untuk n = 22;
  • waktu dp untuk n = 1.000.000;
  • berapa poin yang akan didapat kalau hanya brute yang dikirim, dan berapa kalau hanya dp.

File

Compile dan jalankan:

g++ -std=c++17 -O2 -o mangga projects/03-tiga-pendekatan/starter.cpp
./mangga < projects/03-tiga-pendekatan/contoh-masukan.txt

Sudah selesai?

Kalau ketiga fungsi berjalan, kamu punya contoh kasus yang membuat greedy salah, dan kamu bisa menjelaskan kenapa DP tidak terkena masalah yang sama — proyek ini selesai.

Lanjut ke Bab 14 — Modulo dan teorema-teoremanya, tempat matematika soal OSN mulai dibahas sendiri.