Remendo

remendo.cpp

#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;
}