- 最大子矩阵
兄弟们,60WA,帮忙看看
- 2024-4-12 13:58:57 @
#include <bits/stdc++.h>
using namespace std;
int a[105][105],b[105][105],f[105][105],mx = -1e7;
int main(int argc, char **argv){
// 前缀和:b[x][y] = a[x][y] + b[x - 1][y] + b[x][y - 1] - b[x - 1][y - 1];
// 区间和:a[x2][y2] = b[x2][y2] - b[x2][y1 - 1] - b[x1 - 1][y2] + b[x1 - 1][y1 - 1];
int n;
cin >> n;
for (int x = 1;x <= n;x++){
for (int y = 1;y <= n;y++){
cin >> a[x][y];
b[x][y] = a[x][y] + b[x - 1][y] + b[x][y - 1] - b[x - 1][y - 1]; // 前缀和
}
}
for (int x2 = 1;x2 <= n;x2++){
for (int y2 = 1;y2 <= n;y2++){
for (int x1 = 1;x1 <= n;x1++){
for (int y1 = 1;y1 <= n;y1++){
f[x2][y2] = max(f[x2][y2],b[x2][y2] - b[x2][y1 - 1] - b[x1 - 1][y2] + b[x1 - 1][y1 - 1]); // 找最大的区间
}
}
mx = max(mx,f[x2][y2]);
}
}
cout << mx;
return 0;
}
0 comments
No comments so far...
Information
- ID
- 767
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 35
- Accepted
- 14
- Uploaded By