# 題目: UVa 11951 - Area

# 題目說明

有一個 N * M 大小的矩陣,求 子矩陣合 <= K最大子矩陣範圍


INPUT:
第一行輸入一個整數 T ,代表測資數
每筆測資第一行有三個整數 NMK
接下來有 N * M 個整數,代表矩陣的值


OUTPUT:
輸出 子矩陣合 <= K最大子矩陣範圍

# 解題方法

先建表儲存矩陣的值

2D最大子矩陣合 透過 2 層迴圈壓縮成 1D最大子矩陣合 的問題

以一個變數 top 控制起點,若目前 localmax > K 則將範圍下移一格
計算目前的範圍及子矩陣合,最後儲存最大的範圍至 maxS 、最小的值至 maxP

# 參考程式

#include <iostream>
#include <climits>
#include <memory.h>
using namespace std;
int T, N, M, K;
int l, r, maxS, maxP;
int G[101][101];
int sum[101];
// Kadane's Algorithm
void max1d()
{
	int top = 0, localsum = 0;
	for (int i = 0; i < N; ++i)
	{
		localsum += sum[i];
		while (localsum > K) localsum -= sum[top++];
		int localS = (r - l + 1) * (i - top + 1);
		if (localS > maxS) maxS = localS, maxP = localsum;
		else if (localS == maxS) maxP = min(maxP, localsum);
	}
}
int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	cin >> T;
	for (int cases = 1; cases <= T; ++cases)
	{
		cin >> N >> M >> K;
		// init
		memset(G, 0, sizeof(G));
		maxS = 0;
		maxP = INT_MAX;
		// store data in graph
		for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> G[i][j];
		for (l = 0; l < M; ++l)
		{
			memset(sum, 0, sizeof(sum));
			for (r = l; r < M; ++r)
			{
				for (int i = 0; i < N; ++i) sum[i] += G[i][r];
				max1d();
			}
		}
		cout << "Case #" << cases << ": " << maxS << " " << maxP << "\n";
	}
	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa-11951/

更新於