# 題目: UVa 11951 - Area
# 題目說明
有一個 N * M
大小的矩陣,求 子矩陣合 <= K
的 最大子矩陣範圍
INPUT:
第一行輸入一個整數 T
,代表測資數
每筆測資第一行有三個整數 N
、 M
、 K
接下來有 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/