Solução por Samyra Almeida
Conhecimentos prévios:
Para resolver esse problema primeiro vamos definir como $$custo[a][b]$$, onde $$a < b$$, como o custo de colocar o intervalo de $$a$$ até $$b$$, inclusive, em uma mesma gôndola, ou seja, as somas dos níveis de não familiaridade entre todos os pares $$i, j$$ onde $$a \leq i < j \leq b$$.
Como $$u_{ij} = u_{ji}$$, podemos concluir que a matriz $$u$$ é espelhada em sua diagonal( da esquerda para a direita). Sabendo disso, só iremos processar o custo de uma das metades. Agora, vamos criar o vetor sum[][] como: $$sum[i][j] =$$ soma de todos elementos dentro do retângulo definido pelas posições $$(1, 1)$$ e $$(i, j)$$, onde:
$$sum[i][j] = sum[i][j – 1] + sum[i – 1][j] + u[i][j] – sum[i – 1][j – 1]$$
Para calcular o $$custo[i][j]$$, sendo $$i < j$$ , iremos fazer:
$$custo[i][j] = sum[j][j] – sum[i – 1][j] – sum[j][i – 1] + sum[i – 1][i – 1]$$
Suponha que $$n = 5$$ e que estamos calculando o $$custo[2][4]$$.
Sabemos que:
$$custo[2][4] = sum[4][4] – sum[1][4] – sum[4][1] + sum[1][1]$$
Note que se descontarmos da parte vermelha (sum[4][4]), imagem da esquerda, a parte amarela mais a verde $$(sum[4][1])$$ e a parte azul mais a verde $$(sum[1][4])$$, os dois últimos na imagem da direita, e somarmos a parte verde $$(sum[1][1])$$, que foi descontada duas vezes. Teremos o dobro do $$custo[2][4]$$, pois a matriz é refletida, ai basta dividir o $$custo[2][4]$$ por dois.
Já que já calculamos a matriz de custo, vamos de definir a $$dp[i][j] =$$ o valor total mínimo de não familiaridade entre as $$j$$-ésimas primeiras pessoas que estão nas $$i$$ primeiras gôndolas.
Suponha que para calcularmos a $$dp[i][j]$$ já sabemos a resposta da $$dp[i – 1][a], \forall \space a \space | \space1 \leq a \leq j$$, e para a $$dp[i][j]$$ adicionamos uma gôndola a mais. Com isso, podemos notar que a resposta de $$dp[i][j]$$ é igual ao mínimo entre um dos estados da $$dp$$ utilizando $$i – 1$$ gôndolas até o $$a – 1$$-ésimo cara na fila mais o custo de colocar da $$a$$-ésima até a $$j$$-ésima pessoa na $$i$$-ésima gôndola. Formalizando, temos:
$$dp[i][j] = min(dp[i – 1][a – 1] + custo[a][j]), \forall \space a \space | \space 1 \leq a \leq j$$
Note que, em cada estado da $$dp$$ passamos por no máximo $$n$$ posições, e como existem $$k*n$$ estados, a complexidade final desse algoritmo é de $$\mathcal{O}(k*n^2)$$. O que é bem ruim. Por isso, iremos utilizar uma técnica de otimização de DP’s chamada Divisão e Conquista. Valhe lembrar que não estamos falando da técnica de programação chamada Divisão e Conquista e sim da Otimização de DP (programação dinâmica).
Para que possamos aplicar Divisão e Conquista, temos que provar que