----------------------------------------------------------------------------------------------------------------------------------------------
惊奇的发现
我以前竟然写过
只不过当时是用贪心做的
4重循环居然还过了
(当时对时限都没太大的印象...)
而这次写的
就是动态规划了
就要优化优化再优化
(其实也就是用惯常的动态规划的思路)
----------------------------------------------------------------------------------------------------------------------------------------------
- 总时间限制:
- 1000ms 内存限制:
- 65536kB
- 描述
- 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如,如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。 输入
- 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127, 127]。 输出
- 输出最大子矩阵的大小。 样例输入
-
40 -2 -7 0 9 2 -6 2-4 1 -4 1 -18 0 -2
样例输出 15 -------------------------------------------------------------------------------------------------------------------------------
#include#include #include using namespace std;int n,a[105][105],b[105],sum,maxx;int hhhh(int a[],int n){ int tot = 0,m = 0; for(int i = 1;i <= n;i++) { tot+=a[i];//模拟加上子矩阵的每一行 if(tot<0)//如果是负数则归0,避免子矩阵和为负数 tot = 0; if(tot>m)//取子矩阵最大的和 m = tot; } return m;//返回最大值m }int main() { scanf("%d",&n); for(int i = 1; i <= n;i++) for(int j = 1;j <= n;j++) scanf("%d",&a[i][j]); for(int i = 1;i <= n;i++) for(int j = i;j <= n;j++) { memset(b,0,sizeof(b));//每处理一次,数组清0 for(int q = 1;q <= n;q++) for(int w = i;w <= j;w++) b[q] += a[w][q];//纵向列之和 sum = hhhh(b,n); if(maxx