Solução Informática - Nível Avançado - Semana 35

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.