Doceria
Comentário por João Pedro Castro
Subtask 2 – $$C_i = E_i = 1$$
Conhecimento prévio necessário:
Como todos os doces tem o mesmo custo, e nesse caso é 1, sempre fazer sentido pegar os $$min(R, N)$$ doces com maior doçura. Para lidar com as mudanças podemos manter um multiset e em cada atualização apagar $$D_{X_i}$$ e adicionar $$F_i$$, para depois pegar os $$min(R, N)$$ doces com maior doçura. A complexidade é $$O(N \cdot (log(N) + min(R, N)))$$.
Clique aqui para ver uma possível implementação.
Subtask 1 – $$E_i = C_{X_i}$$ e $$F_i = D_{X_i}$$
Conhecimento prévio necessário:
Nessa subtask o cenário após toda mudança é o mesmo, logo basta usar uma DP no mesmo modelo da knapsack para calcular a resposta para o problema inicial, e depois imprimir o mesmo valor após cada mudança. A complexidade é $$O(N \cdot R)$$.
Subtask 3 – $$F_i = 0$$
A ideia dessa subtask é a de que nunca faz sentido pegar os doces já atualizados, já que a doçura deles agora é 0. Podemos “renomear” os doces, falando que o primeiro doce a ser atualizado tem número $$N$$, o segundo número $$N – 1$$, etc. Com o último doce a ser atualizado tendo número $$1$$. Agora, podemos rodar uma knapsack normal nessa ordem atualizada, e com $$dp[i][j] =$$ usando os $$i$$ primeiros doces e $$j$$ reais qual a maior doçura atingível. Assim, para a atualização $$k$$ a resposta é $$dp[i – k][R]$$, já que não usamos os últimos $$k$$ doces. A complexidade é $$O(N \cdot R)$$.
Clique aqui para ver uma possível implementação.
Subtask 4 – $$X_i = i$$
Podemos fazer duas knapsacks, com $$pf[i][j] =$$ usando os $$i$$ primeiros doces com seus valores atualizados e $$j$$ reais qual a maior doçura atingível; e $$sf[i][j] =$$ usando os últimos $$i$$ primeiros doces com seus valores não atualizados e $$j$$ reais qual a maior doçura atingível. Assim, para cada atualização $$k$$ sabemos que usaremos uma quantidade $$x \leq R$$ reais nos $$k$$ primeiros doces, conseguindo $$pf[k][x]$$ de doçura, e usaremos $$R – x$$ reais nos últimos $$N – k$$ doces, conseguindo $$sf[N – k][R – x]$$ de doçura. Assim, para cada atualização podemos brutar o $$x$$ ótimo, e deixar $$pf[i][j]$$ e $$sf[i][j]$$ pré-calculados.
Subtask 5 – Sem restrições adicionais
A solução é basicamente a mesma da subtask 4, mas com a ideia adicional da subtask 3 que podemos “renomear” os doces. Assim, renomeamos o primeiro doce a ser atualizado como 1, o segundo como 2, etc, e o último como $$N$$.
Clique aqui para ver uma possível implementação.