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.

1. 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.
2. 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.