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.

	#include <iostream>
	#include <cstring>
	#include <algorithm>

	using namespace std;

	#define MAXN 1100
	#define INF 0x3f3f3f3f

	int n, c, t1, t2, furo[2MAXN], dp[2MAXN][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;
	}

view raw

remendo.cpp

hosted with ❤ by GitHub