Silakan! Bagaimana cara mengatasi pertanyaan ini? (C++)

Inilah pertanyaan yang saya temui saat melakukan latihan sehari-hari:

Petani John mempunyai N ekor sapi dalam satu baris (1≤N≤3⋅10^5). Sayangnya, ada penyakit yang menyebar ke mana-mana. Awalnya, beberapa sapi mulai terinfeksi. Setiap malam, sapi yang terinfeksi menularkan penyakitnya ke sapi-sapi di kiri dan kanannya (jika ada). Sekali seekor sapi terinfeksi, ia tetap terinfeksi. Setelah beberapa malam, Petani John menyadari bahwa masalahnya sudah tidak terkendali, jadi dia menguji sapinya untuk menentukan siapa yang mengidap penyakit tersebut. Temukan jumlah minimum sapi yang mungkin tertular penyakit.

MASUKKAN FORMAT
Baris pertama berisi N, jumlah sapi yang dimiliki Petani John.
Baris berikutnya berisi bitstring karakter N hanya 1 dan 0 dengan mana 1 mewakili sapi yang terinfeksi dan 0 mewakili sapi yang tidak terinfeksi setelah beberapa malam.

FORMAT OUTPUT
Keluarkan bilangan bulat tunggal: jumlah minimum sapi yang mungkin mulai sakit.

SAMPEL MASUKAN:
5
11111
KELUARAN SAMPEL:
1
Misalkan sapi tengah adalah satu-satunya sapi yang mulai terinfeksi. Kemudian sapi-sapi tersebut akan tertular dengan urutan sebagai berikut:

0 malam: 00100 (sapi ketiga pertama kali terinfeksi)
1 malam:01110 (sapi kedua dan keempat sekarang tertular)
2 malam:11111 (sapi pertama dan kelima sekarang tertular)
3 malam:11111 (semua sapi sudah tertular, jadi tidak ada sapi tambahan yang tertular)

Setelah dua malam atau lebih, keadaan akhir sapi akan terlihat seperti masukan. Ada banyak keadaan awal dan jumlah malam lainnya yang dapat menghasilkan keadaan masukan, seperti:

0 malam: 10001
1 malam:11011
2 malam:11111
atau:

0 malam:01001
1 malam:11111
atau:

0 malam:01000
1 malam:11100
2 malam:11110
3 malam:11111
Semua negara bagian awal ini memiliki setidaknya satu sapi yang terinfeksi.

SAMPEL MASUKAN:
6
011101
KELUARAN SAMPEL:
4
Satu-satunya keadaan awal dan jumlah malam yang dapat menyebabkan keadaan akhir ini adalah jika tidak ada malam yang terlewati dan masing-masing dari empat sapi yang terinfeksi di masukan mulai sakit.

SKOR:

* Masukan 3-7: N≤1000
* Input 8-12: Tidak ada batasan tambahan.

Saya perlu menyelesaikan pertanyaan ini menggunakan C++.

Apa yang saya coba:

Saya sudah mencoba memikirkan solusinya, tapi sekarang saya pikir saya hanya tahu bagaimana melakukan kebalikan dari pertanyaan ini 🙁 Saya tidak bisa memikirkan solusinya. Tolong bantu saya! Saya tipe orang yang perlu pecahkan pertanyaan ketika saya melihatnya. Saya hanya seorang pemula, jadi tolong bantu!