Solução Zonas de Ataque Independentes

Solução por João Guilherme

Temos novamente um problema de Programação dinâmica. Nesse faremos uma dp com os estados começo do intervalo e fim do intervalo. Para cada intervalo temos alguns casos:

1. O intervalo tem tamanho maior que 3. Nesse caso olhamos para cada 2 outras posições entre o começo e o fim do intervalo, checamos se não temos 3 vermelhos, caso não tenha nós adicionamos à solução o produto entre as soluções dos 3 intervalos que serão formados pelos nossos 4 pontos.
2. O intervalo tem tamanho igual a 3. Então basta checarmos se o intervalo é válido (tem menos que 3 vermelhos) e respondemos de acordo.
3. O intervalo tem tamanho menor que 3, retornamos 1.

Segue o código para melhor entendimento.

https://gist.github.com/jogu99/7901dd44c12c640184710ae3bbc564e8