Solução Remendo

0 Flares Facebook 0 0 Flares ×

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) ot2 (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.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: