Soal yang menarik untuk dibahas kali ini berasal dari UVa 11491 - Erasing and Winning.
Persoalannya sederhana, kita diberikan sebuah bilangan yang besarnya n dan n ~ 100000. Jika kita harus menghapus d dijit, maka berapa bilangan terbesar yang dapat kita hasilkan?
Karena banyaknya dijit cukup besar, jelas bahwa brute force \(O(2^n)\) tidak akan bekerja.
Observasi 1:
Solusi optimal ketika d dijit dihapus sama saja dengan: bilangan terbesar yang dapat dihasilkan bila kita menghapus 1 dijit dari solusi optimal saat (d-1) dijit dihapus. Oleh karena itu, kita dapat menghapus 1 per 1 dan di setiap langkahnya harus optimal. Observasi ini memunculkan aroma greedy pada persoalan ini.
Persoalannya sederhana, kita diberikan sebuah bilangan yang besarnya n dan n ~ 100000. Jika kita harus menghapus d dijit, maka berapa bilangan terbesar yang dapat kita hasilkan?
Karena banyaknya dijit cukup besar, jelas bahwa brute force \(O(2^n)\) tidak akan bekerja.
Observasi 1:
Solusi optimal ketika d dijit dihapus sama saja dengan: bilangan terbesar yang dapat dihasilkan bila kita menghapus 1 dijit dari solusi optimal saat (d-1) dijit dihapus. Oleh karena itu, kita dapat menghapus 1 per 1 dan di setiap langkahnya harus optimal. Observasi ini memunculkan aroma greedy pada persoalan ini.
