8601 最大长方体问题.zip_M?n_givenyze_plasticztr_算法

#include "pch.h" #include<iostream> using namespace std; int MaxSum1(int p, int* a); int MaxSum2(int n, int p, int** a); int MaxSum3(int m, int n, int p, int*** a); int main() { int m, n, p, ***a; cin >> m >> n >> p; a = new int**[m + 1]; for (int i = 1; i <= m; i++) a[i] = new int*[n + 1]; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) a[i][j] = new int[p + 1]; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= p; k++) cin >> a[i][j][k]; cout << MaxSum3(m, n, p, a); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) delete[] a[i][j]; for (int i = 1; i <= m; i++) delete[] a[i]; delete[] a; return 0; } int MaxSum1(int p, int* a) { int sum = 0, b = 0; for (int i = 1; i <= p; i++) { if (b > 0) b += a[i]; else b = a[i]; if (b > sum) sum = b; } return sum; } int MaxSum2(int n, int p, int** a) { int sum = 0; int *b = new int[p + 1]; for (int i = 1; i <= n; i++) { for (int k = 1; k <= p; k++) b[k] = 0; for (int j = i; j <= n; j++) {//i,j 决定MaxSum被调用的次数,n = 3, 则3 + 2 + 1 = 6次 for (int k = 1; k <= p; k++) b[k] += a[j][k]; /* for (int k = 1; k <= p; k++) cout << "i " << i << " j " << j << " " << "[" << b[k] << "] "; cout << endl; */ int max = MaxSum1(p, b); if (max > sum) { sum = max; //cout << "i " << i << " j " << j << " " << "sum " << sum << endl; } } //cout << endl; } delete[] b; return sum; } int MaxSum3(int m, int n, int p, int*** a) { int sum = 0; int** c = new int*[n + 1]; for (int i = 1; i <= n; i++) c[i] = new int[p + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) for (int k = 1; k <= p; k++) c[j][k] = 0; for (int l = i; l <= m; l++) {//i,l 决定MaxSum2被调用的次数, 如m = 3, 则3 + 2 + 1 = 6 for (int j = 1; j <= n; j++) for (int k = 1; k <= p; k++) c[j][k] += a[l][j][k]; int max = MaxSum2(n, p, c); //cout << endl; if (max > sum) sum = max; } } for (int i = 1; i <= n; i++)//解除占用 delete[] c[i]; delete[] c; return sum; } /* 标准输入数据: 3 4 5 -61 -10 78 65 -90 9 256 -50 54 -87 87 -1 -1 56 50 7 43 -54 -32 67 61 -10 7 65 -90 9 23 -50 54 -87 87 -1 -1 56 -3 7 43 -54 82 67 -61 -10 -93 65 -90 9 76 -50 54 78 8 -1 -1 56 60 7 8 -8 -32 -4 标准输出答案: 1|896 */