Leia o enunciado antes de continuarmos.
Sabemos que:
Fazer uma busca exaustiva de todos os N pontos de corte implicaria uma complexidade O(N!) o que é incomportável para N=50 (50! ~ 3x10^64).
Este problema, porém, pode ser definido recursivamente.
Seja o valor do melhor corte entre os pontos left e right designado por costs[left][right]. Como calcular o melhor ponto para cortar o stick entre left e right?
Admitindo que soubéssemos que o melhor ponto para cortar fosse i, com left < i < right, o custo seria dado por:
costs[left][right] = costs[left][i] + costs[i][right] + (cuts[right] - cuts[left])
onde a expressão cuts[right] - cuts[left] denota o tamanho do pedaço do stick que estamos a considerar.
Mas, claro, nós não sabemos à partida o melhor ponto i para cortar! Temos de o calcular. Felizmente, o número de opções que temos não são muitas: são apenas os pontos de corte entre left e right (um conjunto de opções proporcional a L). Temos apenas de as calcular a todas, e guardar a opção com menor custo. Atualizando a expressão acima:
costs[left][right] = min [ costs[left][i] + costs[i][right] + (cuts[right] - cuts[left]) ]
left<i<right
Esta é a definição recursiva que precisamos saber para aplicar programação dinâmica.
Falta-nos só o caso base. Ora o caso mais simples é quanto o stick não tem pontos de corte (ou seja, quando o right é o ponto de corte logo a seguir ao left). Neste caso o seu custo é zero:
costs[left][right] = 0 , left+1==right
Também observamos que subproblemas distintos partilham subsubproblemas. Por exemplo, o custo entre o 1º e o 5º pontos de corte partilha subproblemas com o custo entre o 3º e o 6º pontos de corte.
Portanto, usamos a técnica da memorização para guardar as soluções dos subproblemas intermédios, de forma a aumentar a velocidade de cálculo das respostas.
A seguinte função calcula o custo óptimo para o subproblema costs[left][right]:
static final int UNKNOWN = 0;
static void computeSols(int left, int right, int[] cuts, int[][] costs) {
if (costs[left][right] != UNKNOWN) // already computed!
return;
if (left+1 == right) { // base of recursion
costs[left][right] = 0;
return;
}
int result = Integer.MAX_VALUE;
for (int i=left+1; i<right; i++) { // search which i-th cut is best
computeSols(left, i, cuts, costs);
computeSols(i, right, cuts, costs);
result = Math.min(result, // keep minimum
costs[left][i] + costs[i][right] + cuts[right] - cuts[left]);
}
costs[left][right] = result; // don't forget to save solution for future use!!
}
Uma última nota: nós queremos calcular o custo óptimo do stick original, que começa na posição 0 e termina na posição L. Na nossa notação isso significa calcular costs[0][N+1] (dado que juntamos estes dois "pontos de corte" aos N pontos de corte iniciais). Por isso, adicionamos estes dois extremos aos pontos de corte originais, i.e., juntamos esses dois valores ao array cuts[ ] que é preenchido pela leitura do input.
Resta-nos ler os dados de input; inicializar as estruturas de forma adequada e realizar os cálculos:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int L = sc.nextInt(); // stick size: 1 <= L < 1000
if (L==0)
break;
int N = sc.nextInt(); // 1 <= N <= 50
int[] cuts = new int[N+2]; // define cutting places array
for(int i=1; i<N+1; i++) // read cutting points
cuts[i] = sc.nextInt();
cuts[0] = 0; // add extremities to compute costs[0][N+1]
cuts[N+1] = L;
int[][] costs = new int[N+2][N+2];
computeSols(0, N+1, cuts, costs);
System.out.println("The minimum cutting is " + costs[0][N+1] + ".");
}
sc.close();
}
Referência: Steven Halim - Competitive Programming 3