Phidias

Phidias, o conhecido escultor grego, prepara mais uma das suas obras. Para isso, ele precisa de painéis rectangulares de mármore de tamanho C1 x H1, C2xH2, ..., Cn x Hn.

Recentemente, Phidias recebeu uma grande e rectangular peça de mármore, que vai cortar de modo a formar as peças mais pequenas que necessita. Qualquer pedaço de mármore (a peça inicial ou qualquer placa obtida após o primeiro corte) pode ser cortado ou na horizontal, ou na vertical em duas outras placas com largura e altura inteiras. Esta é a única forma de cortar peças, e as peças não podem ser coladas. Como a mármore tem um padrão, as placas não podem ser rodadas: se ele corta uma placa de tamanho A x B, não pode ser usada como uma placa de tamanho B x A (excepto se A = B, obviamente) Ele pode fazer 0 ou mais placas de cada um dos tamanhos pretendidos. (é um monumento bastante grande)

Um pedaço de mármore é desperdiçado se, no final de todos os cortes, não possui as dimensões necessárias. Phidias questiona-se sobre qual a melhor maneira de cortar a peça, de modo a minimizar a área desperdiçada.

Como um exemplo, assumam que na figura que se segue a largura inicial era 21 e a altura 11. Os tamanhos das peças necessárias são: 10x4, 6x2, 7x5, 15x10. A área mínima desperdiçada é 10, e a figura mostra uma possível sequência de cortes com essa área desperdiçada.

O objectivo é fazer um programa que dada uma peça original e as dimensões das placas necessárias, calcule a área mínima desperdiçada.

Explicação de Input

A primeira linha do input contem dois inteiros: L, a largura da placa original, e H, a altura da placa. A segunda linha contem um inteiro, N, o número de diferentes tamanhos possíveis. As seguintes N linhas contém os tamanhos das placas. Cada linha com dois inteiros: Li e Hi, respectivamente a largura e a altura da placa correspondente.

Explicação de Output

Um único inteiro, a área mínima desperdiçada.

Exemplo de input/output

Input

21 11
4
10 4
6 2
7 5
15 10

Output

10

Restrições

O programa deve responder com sucesso a um input que siga estes limites: 1 <= L,H <= 600 1 <= N <= 200 1 <= Li <= L 1 <= Hi <= H

Soluções

C

Solução submetida por warrior.

#include <stdio.h>
#include <string.h>

#define MAX 605

int m[MAX][MAX];

int l,c;

void ler() {
  int n,a,b;
  memset(m,0xFF,sizeof(m));
  scanf("%d %d",&l,&c);
  scanf("%d",&n);
  for (int i=0;i<n;i++) {
    scanf("%d %d",&a,&b);
    m[a][b]=0;
  }
}

void solve() {
  int min;
  for (int i=1;i<=l;i++) {
    for (int j=1;j<=c;j++) {
      if (m[i][j]==0)
    continue;
      min=i*j;
      for (int k=1;k<i;k++) 
    if (min>m[k][j]+m[i-k][j]) 
      min=m[k][j]+m[i-k][j];
      for (int k=1;k<j;k++)
    if (min>m[i][k]+m[i][j-k])
      min=m[i][k]+m[i][j-k];
      m[i][j]=min;
    }
  }
}

int main() {
  ler();
  solve();
  printf("%dn",m[l][c]);
  return 0;
}

C++

Solução submetida por mogers.

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 601
using namespace std;

int dp[MAX][MAX];   // desperdicio com uma peca LxH

int calcula( int L , int H ) {
    int & r = dp[L][H] , i ;
    if ( r >= 0 )       return r;     // o desperdicio com estas dimensoes ja foi calculado, retorna o valor da tabela
    if ( L == 0 || H == 0 ) return r = 0; // tamanho 0 e' o mesmo que nada

    r = L * H;  // tudo desperdicado

    for (i = 1 ; i < L ; i++)   // corte horizontal
        r = min( r , calcula( i , H ) + calcula( L-i , H ) );
    for (i = 1 ; i < H ; i++)   // corte vertical
        r = min( r , calcula( L , i ) + calcula( L , H-i ) );
    return r ;
}
int main()
{
    memset( dp , -1 , sizeof(dp) );
    int L , H , N , i , j;
    cin >> L >> H >> N;
    while (N--) {
        cin >> i >> j;
        dp[i][j] = 0;   // pecas com dimensoes necessitadas nao provocam desperdicio
    }
    cout << calcula( L , H ) << endl;
    return 0;
}