Solução Remendo

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Usaremos uma abordagem um pouco diferenciada de DP para resolvermos este problema. Se você nunca ouviu falar de DP, clique aqui para ver a aula do Curso Noic sobre o assunto. Imagine a função $$custo(int ini, int fim)$$, que retorna o menor custo para remendarmos o intervalo $$[ini, fim]$$ do pneu, onde $$ini$$ e $$fim$$ são índices de furos. Como o pneu é circular, duplicaremos os furos, de modo que o primeiro furo, por exemplo, aparece uma vez no começo e outra vez após a primeira aparição do último furo.

De maneira simples, salvaremos a coordenada do furo de índice $$i$$ em $$furo[i]$$, depois duplicaremos o vetor $$furo$$ (adicionando $$c$$ a cada coordenada), fazendo com que $$furo[i+n]$$ receba $$furo[i]+c$$. Deste modo, vamos testar a todas as possibilidades da seguinte maneira: para cada um dos furos iremos testar cobri-lo com um dos remendos, o que “transforma o círculo em uma reta”, pois agora só precisamos cobrir o resto do pneu, desde o fim do remendo até o seu começo, um intervalo que pode ser representado pela nossa função $$custo$$. Seja $$busca(int x)$$ uma função que retorna o índice do primeiro furo que está em uma coordenada maior que $$x$$. Deste modo, o custo de usar primeiro o remendo $$t1$$ no furo $$i$$, por exemplo, é $$t1+custo(busca(furo[i]+t1), i+n-1)$$, pois procuramos o próximo furo depois do fim do remendo $$(furo[i]+t1)$$ até que demos a volta inteira no pneu e voltamos para o começo do remendo $$(i+n-1)$$.

Vamos agora implementar a função $$custo$$. Ela será uma DP no estilo Top-Down. Se $$ini>fim$$, não há mais remendo a cobrir, logo retornamos $$0$$. Agora, basta ver se usamos o remendo $$t1$$ ou $$t2$$ para cobrir o furo de índice $$ini$$. Ou seja, seja $$prox1$$ o próximo furo que devemos cobrir se usarmos o remendo $$t1$$, temos que $$prox1 = busca(furo[ini]+t1)$$. Seja $$prox2 = busca(furo[ini]+t2)$$ o mesmo para o remendo $$t2$$. Temos que a melhor maneira de cobrir o intervalo será o mínimo entre o custo de usar o remendo $$t1$$ (custo $$t1$$ de usar o remendo mais $$custo(prox1,fim)$$ para terminamos de cobrir o pneu) o$$t2$$ ($$t2+custo(prox2,fim)$$, analogamente).

Agora, basta implementarmos a função $$busca$$ de maneira eficiente. Basta fazermos uma busca binária pelo valor de $$x$$ no vetor $$furo$$, o que pode ser feito com a função $$upper_bound$$. Se você não conhece  algoritmo da busca binária, clique aqui para ver a aula do Curso Noic sobre o assunto. Segue o código para melhor entendimento.

https://gist.github.com/rogerioagjr/b9ec922163c6638092a0