Solução por Lúcio Figueiredo
Conhecimento prévio necessário:
Uma das grandes dificuldades presentes nesse problema é o valor alto das constantes $$W$$, $$B$$ e $$X$$. Isso nos impede de usar, por exemplo, algum tipo de programação dinâmica que dependa de tais constantes nos seus estados.
No entanto, há dois valores “pequenos” no problema: $$n$$ (que é no máximo $$10^3$$) e o somatório de pássaros nas árvores (no máximo $$10^4$$). Vamos explorar este fato, pensando em algum tipo de programação dinâmica que use estas constantes pequenas em seus estados.
Vamos então definir a seguinte DP: $$dp[i][j]$$ é a quantidade máxima de magia que podemos obter no momento em que saímos da árvore $$i$$ e vamos para a árvore $$i+1$$, assumindo que já conseguimos chamar $$j$$ pássaros.
Note que, caso seja possível calcular a DP de maneira eficiente, a resposta do problema é o máximo valor $$j$$ tal que $$dp[n][j] \geq 0$$, já que só podemos chamar uma quantidade de pássaros se em todos os momentos estivermos com uma quantidade positiva de pontos de magia. Portanto, o que resta é achar uma maneira eficiente de calcular a DP.
Imagine que acabamos de chegar na árvore $$i$$, já chamamos $$j$$ pássaros e vamos chamar $$k$$ dentre os $$c_i$$ pássaros na árvore $$i$$ ($$0 \leq k \leq c_i$$). Ignorando o fato de que há uma capacidade máxima de magia, podemos obter a seguinte recorrência:
$$dp[i][j+k] = dp[i-1][j] + X – custo[i] \cdot k$$
.
Isto se deve ao fato de que ao $$dp[i-1][j]$$ já contém a quantidade de magia que possuíamos logo após sair da árvore $$i-1$$. Após escolhermos $$k$$ pássaros na árvore $$i$$, perdemos $$custo[i] \cdot k$$ de magia e ao prosseguirmos da árvore $$i$$ para a $$i+1$$, ganhamos $$X$$ pontos de magia.
O único problema restante é a capacidade máxima de magia. Porém, podemos facilmente lidar com isso. Perceba que, se usarmos $$j+k$$ pássaros, a capacidade de magia que possuíremos é $$B \cdot (j+k) + W$$, pois possuíamos capacidade mágica $$W$$ inicialmente. Logo, se $$dp[i-1][j] + X – custo[i] \cdot k$$ (o valor da recorrência acima) for maior que $$B \cdot (j+k) + W$$ (a capacidade máxima de magia escolhendo $$j+k$$ pássaros), o valor de magia que obteremos é exatamente a capacidade máxima de magia. Caso contrário, o valor de magia será o valor da recorrência acima.
O que resta analisar é a complexidade da solução. Como a DP possui estados de complexidade $$O(n)$$ e $$O(c)$$, (onde $$c$$ é o maior valor $$c_i$$) e há $$c_i$$ transições na $$i$$-ésima árvore (precisamos escolher um $$k$$ entre $$0$$ e $$c_i$$), em uma primeira análise podemos afirmar que a complexidade será $$O(n \cdot c^2)$$. Porém, na verdade, a complexidade da DP será $$O(c \cdot (\sum_{i=1}^n c_i))$$, e esté valor é, nó máximo, $$10^4 \cdot 10^4 = 10^8$$. Portanto, a solução é eficiente.
Confira o código abaixo para melhor entendimento:
https://gist.github.com/luciocf/87bee39545d5aaf81d41bf5eceaa755f