競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 108 - Maximum Sum

- 問題概要

N*Nの重みつき正方形、もとい行列が与えられます。
考えうる部分行列の要素の和の最大値を求めてください。

- 解法

部分累積和問題の基礎中の基礎の問題です。
入力で与えられる行列のi行j列目の要素をm(i,j)とし、
(1,1)から始まるi*jの大きさの部分行列の要素の和をd(i,j)とします。
d(i,j)について、i*j=0のときd(i,j)=0とします。
すると、d(i,j)=d(i,j)+m(i-1,j)+m(i,j-1)-m(i-1,j-1)が成り立ちます。

次に、(w,h)から始まるi*jの大きさの部分行列の要素の和をr(w,h,i,j)とすると、
r(w,h,i,j)=d(w+i-1,h+j-1)-d(w-1,h+j-1)-d(w+i-1,h-1)+d(w-1,h-1)
として求められます。
これを用いて全ての考えうるr(w,h,i,j)の最大値を求めれば解が求められます。

- ソースコード

#include<iostream>
#include<algorithm>

using namespace std;

#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);

int r[101][101];
int N;
inline int solve(){
	int ans = -(1 << 30);
	reE(i, 1, N){
		reE(j, 1, N)r[i][j] = r[i][j] + r[i - 1][j] + r[i][j - 1] - r[i - 1][j - 1];
	}
	rT(i, N)rT(j, N)
		reE(w, i + 1, N)reE(h, j + 1, N)
		ans = max(ans, r[i][j] + r[w][h] - r[i][h] - r[w][j]);
	return(ans);
}

int main(void){
	cin >> N;
	reE(i, 1,N)reE(j,1, N)cin >> r[i][j];
	cout << solve() << endl;
	return(0);
}