Solução Zonas de Ataque Independentes

0 Flares Facebook 0 0 Flares ×

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.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: