题意 : 给你一个n*n的矩阵,让你找一个子矩阵要求和最大。
思路 : 这个题都看了好多天了,一直不会做,今天娅楠美女给讲了,要转化成一维的,也就是说每一列存的是前几列的和,也就是说
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
处理后就是:
0 -2 -9 -9
9 11 5 7
-4 -3 -7 -6
-1 7 7 5
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; int sum[][] ;
int main()
{
int n ,m;
while(~scanf("%d",&n))
{
memset(sum,,sizeof(sum)) ;
for(int i = ; i <= n ; i++)
{
for(int j = ; j <= n ; j++)
{
scanf("%d",&m) ;
sum[i][j] = sum[i-][j]+m ;
}
}
int ans = - ;
for(int i = ; i <= n ; i++ )
for(int j = i ; j <= n ; j++)
{
int cnt = ;
for(int k = ; k <= n ; k ++)
{
cnt += sum[j][k]-sum[i-][k] ;
ans = max(cnt,ans) ;
if(cnt < ) cnt = ;
}
}
printf("%d",ans) ;
}
return ;
}