Solução escrita por Caique Paiva
Conhecimento prévio necessário:
- Bitmask DP
Vamos fazer uma dp! A ideia é calcular para cada subconjunto de pessoa dois valores: O número mínimo de subidas no elevador e o peso mínimo do último grupo. Podemos representar cada conjunto por uma bitmask. Portanto, a dp seria
$$pair <int, int> dp[1 << N]$$
Onde $$N = 20$$. Agora, a transição seria o seguinte:
- Dada uma bitmask $$mask$$, vamos percorrer todos os elementos de $$0$$ até $$n-1$$ (Estamos fazendo os valores serem $$0$$ indexados). Seja $$i$$ o elemento que estamos agora
- Se $$i \in mask$$, ou seja, se $$(1 << i) \& mask \neq 0$$, então, suponha que já calculamos a resposta para $$dp[mask \wedge (1 << i)]$$, logo, seja $$pair <int, int> aux$$ uma variável auxiliar, então, temos duas possibilidades.
- Se podemos colocar $$i$$ na última corrida de modo que não estoure o limite do peso do elevador (Ou seja, se $$dp[mask \wedge (1 << i)].second + w[i] \le W$$ onde $$w[i]$$ é o peso da pessoa $$i$$ e $$W$$ é o limite do elevador), então, faça $$aux = \{ dp[mask \wedge (1 << i)].first, dp[mask \wedge (1<<i)].second + w[i] \}$$, pois isso significa colocar $$i$$ na viagem atual.
- Senão, ou seja, colocando $$i$$ na última corrida, isso derrubaria o elevador, então, para colocar $$i$$, temos que começar outra viajem, portanto, faça $$aux = \{dp[mask \wedge (1 << i)].first + 1, w[i]\}$$, pois isso significa subir a viagem atual até o último andar e começar uma nova.
- E portanto, basta comparar $$aux$$ com $$dp[mask]$$, se $$aux$$ for menor que $$dp[mask]$$, então fazemos $$dp[mask] = aux$$. Veja que $$aux$$ ser menor que $$dp[mask]$$ significa que a quantidade de viagens que eu faço em $$aux$$ é menor que a quantidade de viagens que eu faço em $$dp[mask]$$ e, se for a mesma quantidade de viagens, o peso da última viagem em $$aux$$ é menor que o peso da última viagem em $$dp[mask]$$.
Depois de rodar tudo, basta retornar a resposta de
$$dp[(1 << n)-1].first + (dp[(1 << n)-1].second == 0 ? 0 : 1)$$.
($$dp[(1 << n) -1].first$$ retorna a quantidade de vezes que andamos no elevador e se $$dp[(1 << n)-1].second > 0$$ significa que temos uma viagem que ainda não acabou, então, temos que acresentar ela na resposta).
Esse códgio roda em $$O(N2^N)$$, pois temos $$2^N$$ estados de $$dp$$ para calcular, e a transição é em $$O(N)$$.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.