UVa 108 : Maximum Sum

問題リンク：Maximum Sum

問題概要：
N*Nの2次元配列が与えられる
この中から作れる長方形のうちその要素の和が最大のものをみつけよ

解法：
よくあるDP
memo[y][x] := memo[y-1][x] + memo[y][x-1] - memo[y+1][x+1] + array[y][x]

という配列を用意する
arrayは入力で与えられる2次元配列
memoは(0,0)から(x,y)までの長方形の要素の和を表す

後は長方形の左上と右下をループで決めて、memoを以下の様に利用して面積を求める
左上を(x1,y1),右下を(x2,y2)とする
この長方形の要素の和をSとする
S = memo[y2][x2] - (memo[y2][x1-1]+memo[y1-1][x2]) + memo[y1-1][x1-1]
こうして最大のものを記録しておき、出力する

コード：

#define inf (1<<29)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 110
using namespace std;

int N;
int memo[MAX][MAX];
int value[MAX][MAX];

int main()
{
  scanf("%d",&N);
  rep(y,N)rep(x,N)scanf("%d",&value[y][x]);

  rep(y,N)
    {
      rep(x,N)
	{
	  int L = (x-1>=0?memo[y][x-1]:0);
	  int U = (y-1>=0?memo[y-1][x]:0);
	  int D = ((y-1>=0&&x-1>=0)?memo[y-1][x-1]:0);
	  memo[y][x] = L - D + U +value[y][x];
	}
    }

 
  int ans = 0;
  rep(y1,N)
    {
      rep(x1,N)
	{
	  REP(y2,y1,N)
	    {
	      REP(x2,x1,N)
		{
		  int cost1 = (x1-1>=0?memo[y2][x1-1]:0);
		  int cost2 = (y1-1>=0?memo[y1-1][x2]:0);
		  int cost3 = ((x1-1>=0&&y1-1>=0)?memo[y1-1][x1-1]:0);
		  ans = max(ans,
			    memo[y2][x2]-(cost1+cost2)+cost3);
		}
	    }
	}
    }
  cout << ans << endl;

  return 0;
}