108 Maximum Sum ( DP + Inclusion exclusion)

Un claro ejemplo de programacion dinamica e inclusion exclusion. http://uva.onlinejudge.org/external/1/108.html

/* Autor: Rodrigo Burgos Dominguez */

# include 
# include 

int max(int a,int b){ return a > b ? a : b; }

int sum[200][200], data[200][200], n;

main(){
  int x, y, a, b, sol;
  scanf("%d", &n);
  for( x = 0; x < n ; x++)
  for( y = 0; y < n ; y++) scanf("%d", &data[ x ][ y ]);
  memset( sum, 0, sizeof( sum ));
  for( x = n - 1; x >= 0; x--){
    for( y = n - 1; y >= 0 ; y-- ) sum[x][y] = sum[x][y + 1] + data[x][ y ];
    for( y = n - 1; y >= 0 ; y-- ) sum[x][y] += sum[x+1][y]; 
  }
  sol = -(1<<28);
  for( x = 0; x < n; x++)
  for( y = 0; y < n; y++)
  for( a = x; a < n; a++)
  for( b = y; b < n; b++)
    sol = max( sol, sum[x][y] - sum[x][b + 1] - sum[a + 1][y] + sum[a+1][b+1]);
  printf("%d\n", sol);
  return 0; 
}

//

Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com