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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <cstring> | |
| #include <algorithm> | |
| using namespace std; | |
| #define MAXN 1100 | |
| #define INF 0x3f3f3f3f | |
| int n, c, t1, t2, furo[2*MAXN], dp[2*MAXN][2*MAXN]; | |
| // busca binária para achar o primeiro furo depois da coordenada x | |
| int busca(int x){ return (upper_bound(furo+1, furo+2*n+1, x) – furo); } | |
| // função recursiva da DP | |
| int custo(int ini, int fim){ | |
| // se já tiver calculado este estado, retorno o vaor salvo | |
| if(dp[ini][fim]>=0) return dp[ini][fim]; | |
| // se ini>fim, não há o que cobrir, logo retorno zero | |
| if(ini>fim) return dp[ini][fim]=0; | |
| int prox1, prox2; | |
| // calculo os valores de prox1 e prox2 | |
| prox1=busca(furo[ini]+t1); | |
| prox2=busca(furo[ini]+t2); | |
| // retorno o mínimo entre usar os remendos t1 ou t2 para cobrir o furo ini | |
| return dp[ini][fim]=min(t1+custo(prox1,fim), t2+custo(prox2,fim)); | |
| } | |
| int main(){ | |
| // enquanto houer casos de teste na etrada | |
| while(scanf("%d %d %d %d", &n, &c, &t1, &t2)!=EOF){ | |
| // limpe toda a tabela de DP | |
| memset(dp,-1,sizeof(dp)); | |
| // leio a entrada | |
| for(int i=1; i<=n; i++){ | |
| // e duplico o vetor que representa opneu | |
| scanf("%d", &furo[i]); | |
| furo[i+n]=furo[i]+c; | |
| } | |
| int menor=INF; | |
| // para cada furo do pneu | |
| for(int i=1; i<=n; i++){ | |
| int com1=busca(furo[i]+t1); | |
| int com2=busca(furo[i]+t2); | |
| int preco1=t1+custo(com1, i+n-1); | |
| int preco2=t2+custo(com2, i+n-1); | |
| // vejo qual o mais barato entre começar a cobrir o pneu por este furo | |
| // usando o remendo t1 ou t2 | |
| menor=min(menor, min(preco1,preco2)); | |
| } | |
| printf("%d\n", menor); | |
| } | |
| return 0; | |
| } |
Comente