Java教程

#1071. [绍兴2017]沙盘游戏

本文主要是介绍#1071. [绍兴2017]沙盘游戏,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目链接:

http://39.98.219.132:8080/problem/1071

题目大意:

求 n * m 矩阵中和最大的子矩阵

思路:

首先通过二维前缀和建立前缀和矩阵,题目的数据导致暴力跑每个矩阵的值的时间复杂度为 O(n * n * m * m), 会超时,所以进行优化,先从行出发,可以通过 O(n * n) 的方式遍历行的所有组合,再遍历列,求前缀和,当前缀和 <= 0 时,左边的矩阵就可以舍去,直接求解右边矩阵的前缀和显然更大,于是通过这种方式优化掉一个 m

代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 300;
LL n, m, sum[maxn][maxn], num, ans = -1e16;
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){  //构建二维前缀和数组
		for (int j = 1; j <= m; j++){
			scanf("%lld", &num);
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num;
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < i; j++){
			LL p = 0;  //当前找寻的矩阵的左上角位置
			for (int k = 1; k <= m; k++){
				LL t = sum[i][k] - sum[j][k] - sum[i][p] + sum[j][p];
				if (t <= 0) p = k;  //如果前缀和 <= 0 的时候,就可以更新左上角的位置
				ans = max(ans, t);
			}
		}
	}
	cout << ans << "\n";
	return 0;
}
这篇关于#1071. [绍兴2017]沙盘游戏的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!