UVa-10827 : Maximum sum on a torus

問題概要

N*N(N<75)の盤面に数字が埋まっている。盤面はトーラス状に端同士がつながっている。長方形領域に置ける最大の部分和を求める問題。

解法

前処理で累積和を持っておいて全探索する。トーラス云々は4倍にしたテーブルの上でやっておけば特に意識せずに処理できる。計算量はO(N^4)で危ないがそんなに複雑な処理をしてるわけではないので何とか間に合う。

acceptされたコード

計算量O(N^4)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 75;
const int INF = 1<<29;

int N;
int as[MAX_N][MAX_N];
int accum[2*MAX_N+1][2*MAX_N+1];

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			scanf("%d", as[i] + j);
		}
	}

	for(int i=0; i<2*N; i++){
		for(int j=0; j<2*N; j++){
			accum[i+1][j+1] = accum[i+1][j] + accum[i][j+1] - accum[i][j] + as[i%N][j%N];
		}
	}
}

int solve(){
	int ans = -INF;

	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			for(int h=1; h<=N; h++){
				for(int w=1; w<=N; w++){
					ans = max(ans, accum[i+h][j+w] - accum[i+h][j] - accum[i][j+w] + accum[i][j]);
				}
			}
		}
	}

	return ans;
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		printf("%d\n", solve());
	}

	return 0;
}