Solução escrita por Márcio Vitor
Conhecimentos prévios:
Vamos usar programação dinâmica para resolver o problema! 🙂
Seja $dp[i][tipo]$ = a quantidade de tinta usada para pintar uma árvore de altura $i$ tal que a primeira tesoura está aberta se $tipo = 1$ e fechada se $tipo = 0$.
Caso base: $dp[0][0] = dp[0][1] = 0$ não precisa de tinta para uma árvore vazia.
Transição:
- $dp[i][0] = dp[i-1][1] + 1$ (só precisamos subir com o spray e resolver para a próxima árvore.
- $dp[i][1] = dp[i-1][0] + i+2$ (temos que gastar 3 sprays na própria tesoura da base e mais $i-1$ para descer na árvore da direita).
Compleixdade: $\mathcal{O}(N)$