【範例】DP: Max 2D Range Sum
【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d206
【解題想法】DP、排容
【優化的做法】前綴
#include <iostream>
using namespace std;
long long n, a[105][105], ans, total;
int main() {
while (cin >> n){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> a[i][j];
a[i][j] += a[i][j-1];
}
}
ans = 0;
for (int i = 0; i < n; i++){
for (int j = i+1; j <= n; j++){
total = 0;
for (int k = 1; k <= n; k++){
total += a[k][j]-a[k][i];
ans = max(ans, total);
if (total < 0) total = 0;
}
}
}
cout << ans << "\n";
}
}
【原始做法】枚舉
- (Line 12~19) 一邊讀入測資，一邊進行DP的狀態轉移計算。
- (Line 22~31) 枚舉所有可能的子區域 (sub-rectangle)，左上角座標 (i, j)，右下角座標 (k, l)。
#include <iostream>
#include <algorithm>
using namespace std;
int a[101][101];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cin >> a[i][j];
if (i > 0) a[i][j] += a[i-1][j];
if (j > 0) a[i][j] += a[i][j-1];
if (i > 0 && j > 0) a[i][j] -= a[i-1][j-1];
}
}
int maxSum = -127*100*100;
int subRect = 0;
for (int i=0; i<N; i++)
for (int j=0; j<N; j++)
for (int k=i; k<N; k++)
for (int l=j; l<N; l++) {
subRect = a[k][l];
if (i > 0) subRect -= a[i-1][l];
if (j > 0) subRect -= a[k][j-1];
if (i > 0 && j > 0) subRect += a[i-1][j-1];
maxSum = max(maxSum, subRect);
}
cout << maxSum << endl;
}
return 0;
}