最大加权矩形的算法和动态规划方程

来源：百度知道 编辑：UC知道 时间：2024/05/26 04:02:44
、最大加权矩形
给定一个正整数n（ n<=100），然后输入一个N*N矩阵。求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。矩阵的每个元素属于[-127,127]
例：
0 –2 –7 0 在左下角： 9 2
9 2 –6 2 -4 1
-4 1 –4 1 -1 8
-1 8 0 –2 和为15
输入：
第一行：n，接下来是n行n列的矩阵。
输出：最大矩形（子矩阵）的和。
样例：
输入：
4
0 –2 –7 0
9 2 –6 2
-4 1 –4 1
–1 8 0 –2
输出：
15

只有展开才可以看到排版
#include <cstdio>
#include <cmath>

using namespace std;

const int XJ = -9000000;
const int maxn = 3000 + 5;

int n, m, a[maxn][maxn], rowsum[maxn][maxn], area, ans;

int main(){
int i, j, k;
scanf("%d %d", &n, &m);

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = 1;

for (int i = 1; i <= m; i++){
int x, y;
scanf("%d %d", &x, &y);
a[x][y] = XJ;
}

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
rowsum[i][j] = rowsum[i][j-1] + a[i][j];
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++){
area = 0;
for (k = 1; k <= n; k++)
if (k){
area += rowsum[k][j] - rowsum[k][i-1];