Escrito por Enzo Dantas
Conhecimento prévio necessário:
A ideia mais básica (força bruta) para resolver esse problema é testar todas as possíveis entradas, o que teria uma complexidade de $${N\choose K} * N$$ ($${N\choose K}$$ para conseguir todos as combinações de entradas possiveis e $$N$$ para simular cada uma delas). Antes de tudo, perceba como essa ideia calcula muitas coisas repetidas e pense como poderíamos calcular um certo estado (combinação de entradas) rapidamente baseado em outro estado “menor”. Sendo assim, temos duas partes do problema que temos que resolver: 1) Como simular uma combinação de entradas e 2) Como otimizar a ideia de força bruta.
Como simular uma combinação de entradas
Primeiramente, usaremos o truque de duplicar o array para simular um círculo.
Assuma que temos uma entrada na posição $$e$$ e outra na posição $$f$$. Perceba que uma pessoa no salão $$j$$ $$(e \leq j < f)$$ vai ter uma desconforto $$j-e$$. Logo, um salão $$j$$ que contém $$v_{j}$$ pessoas vai gerar um grau de desconforto de $$v_{j} * (j-e)$$. Sendo assim, para calcular o desconforto em relação a uma entrada, faremos um for começando de $$e$$ e adicionar $$v[i] * (i-e)$$ ($$e\leq i < f$$) ao contador de desconforto. As salas depois de $$f$$ são calculadas em relação a $$f$$.
Como otimizar a ideia de força bruta
Usaremos uma DP do tipo $$dp_{l, r, k}$$ = mínimo desconforto gerado tal que há uma entrada no índice $$l$$, a primeira entrada de todas está no índice $$r+1$$ e ainda podemos criar $$k$$ entradas.
Inicialmente, vamos brutar o $$r$$, ou seja, vamos testar colocar a primeira entrada em todos os índices. Testaremos todas as combinações de entradas da seguinte maneira: se estamos no estado (l, r, k) tal que $$k \geq 1$$, podemos criar uma entrada em qualquer índice $$j$$ entre $$l+1$$ e $$r$$, o que nos leva ao estado $$dp_{j, r, k-1}$$. Além disso, quando criamos uma entrada em $$j$$ levamos em conta o desconforto das salas entre $$e$$ e $$j$$. Sendo assim, formalmente, $$dp_{l, r, k} = min(cont + dp_{j, r, k-1})$$, tal que $$cont$$ é o desconforto das salas entre $$e$$ e $$j$$.
Os casos base são quando $$k=0$$, ou seja, não podemos criar nenhuma outra entrada então apenas simularemos como descrito acima e quando $$l=r$$, onde o resultado é sempre 0.
É facil ver que a DP possui $$N^2*K$$ estados. Como em cada estado fazemos um for de tamanho possivelmente $$N$$, a complexidade da DP é $$O(N^2*K*N)$$ = $$O(N^3*K)$$.
Recomendamos que você tente implementar o problema antes de ver o código. Para conferi-lo, clique aqui.