这数据量和这时限,很显然暴力是最好的解法,预处理前缀和,n方复杂度秒过。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int N = 1001; 7 int a[N][N]; 8 int m, n, x, y; 9 10 int get( int i, int j ) 11 { 12 int x1 = a[i + x - 1][j + y - 1]; 13 int x2 = a[i + x - 1][j - 1]; 14 int x3 = a[i - 1][j + y - 1]; 15 int x4 = a[i - 1][j - 1]; 16 return x1 - x2 - x3 + x4; 17 } 18 19 int main () 20 { 21 int t; 22 scanf("%d", &t); 23 while ( t-- ) 24 { 25 scanf("%d%d%d%d", &m, &n, &x, &y); 26 for ( int i = 1; i <= m; i++ ) 27 for ( int j = 1; j <= n; j++ ) 28 scanf("%d", &a[i][j]); 29 for ( int i = 1; i <= m; i++ ) 30 for ( int j = 1; j <= n; j++ ) 31 a[i][j] += a[i][j - 1]; 32 for ( int i = 1; i <= m; i++ ) 33 for ( int j = 1; j <= n; j++ ) 34 a[i][j] += a[i - 1][j]; 35 int ans = -999999999; 36 for ( int i = 1; i + x - 1 <= m; i++ ) 37 for ( int j = 1; j + y - 1 <= n; j++ ) 38 ans = max( ans, get( i, j ) ); 39 printf("%d ", ans); 40 } 41 return 0; 42 }