¡Por favor! ¿Cómo resolver esta pregunta? (C++)

Aquí hay una pregunta que encontré mientras hacía una práctica diaria:

El granjero John tiene N vacas en una línea (1≤N≤3⋅10^5). Desafortunadamente, hay una enfermedad que se está extendiendo por todas partes. Inicialmente, algunas vacas empiezan infectadas. Cada noche, una vaca infectada transmite la enfermedad a las vacas de izquierda y derecha (si existen). Una vez que una vaca está infectada, permanece infectada. Después de algunas noches, el granjero John se da cuenta de que el problema se ha salido de control, por lo que examina a sus vacas para determinar quién tiene la enfermedad. Encuentre el número mínimo de vacas que podrían haber comenzado con la enfermedad.

FORMATO DE ENTRADA
La primera línea contiene N, la cantidad de vacas que tiene el granjero John.
La siguiente línea contiene una cadena de bits de N caracteres de solo 1 y 0, donde un 1 representa una vaca infectada y un 0 representa una vaca no infectada después de un cierto número de noches.

FORMATO DE SALIDA
Genera un único número entero: el número mínimo de vacas que podrían haber comenzado con la enfermedad.

ENTRADA DE MUESTRA:
5
11111
SALIDA DE MUESTRA:
1
Supongamos que la vaca del medio fuera la única que empezó infectada. Luego las vacas quedarían infectadas en el siguiente orden:

0 noches: 00100 (la tercera vaca está inicialmente infectada)
1 noche:01110 (la segunda y cuarta vacas ahora están infectadas)
2 noches:11111 (la primera y la quinta vaca ahora están infectadas)
3 noches: 11111 (todas las vacas ya estaban infectadas, por lo que no hay vacas adicionales infectadas)

Después de dos o más noches, el estado final de las vacas se parecería al de entrada. Hay muchos otros estados iniciales y número de noches que podrían haber producido el estado de entrada, como por ejemplo:

0 noches: 10001
1 noche:11011
2 noches:11111
o:

0 noches:01001
1 noche:11111
o:

0 noches:01000
1 noche:11100
2 noches:11110
3 noches:11111
Todos estos estados iniciales contienen al menos una vaca infectada.

ENTRADA DE MUESTRA:
6
011101
SALIDA DE MUESTRA:
4
El único estado inicial y número de noches que podría haber llevado a este estado final es si no han pasado noches y cada una de las cuatro vacas infectadas en la entrada comenzó con la enfermedad.

PUNTUACIÓN:

* Entradas 3-7: N≤1000
* Entradas 8-12: Sin restricciones adicionales.

Necesitaba resolver esta pregunta usando C++.

Lo que he probado:

Intenté pensar en una solución, pero ahora creo que solo sé cómo hacer lo contrario de esta pregunta 🙁 No puedo pensar en una solución. ¡Por favor ayúdenme! Soy el tipo de persona que necesita Resuelve una pregunta cuando la veo. Soy solo un principiante, ¡así que por favor ayuda!