思路:
不难发现,对矩阵中的数字求和实际上是先分别对a,b两个数列中对应子段的元素求和再相乘。题目是要求在和不超过给定值的情况下使选出的矩阵面积最大。我们反其道而行之,考虑在子段长度一定的情况下,和最小是多少。具体来说,首先分别计算a的长度为1,2,...,n的子段中的和的最小值,记为min1[i](i = 1, 2, ..., n)。对b做类似处理得到min2[i](i = 1, 2, ..., m)。然后枚举min1和min2的所有组合即可得出答案。
实现:
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 typedef long long ll; 5 const int MAXN = 2005; 6 const int MAXM = 2005; 7 int a[MAXN], b[MAXM], n, m; 8 ll sum1[MAXN], sum2[MAXM], min1[MAXN], min2[MAXM], x; 9 int main() 10 { 11 while (cin >> n >> m) 12 { 13 memset(sum1, 0, sizeof sum1); 14 memset(sum2, 0, sizeof sum2); 15 memset(min1, 0x3f, sizeof min1); 16 memset(min2, 0x3f, sizeof min2); 17 for (int i = 1; i <= n; i++) 18 { 19 cin >> a[i]; 20 sum1[i] = sum1[i - 1] + a[i]; 21 } 22 for (int i = 1; i <= m; i++) 23 { 24 cin >> b[i]; 25 sum2[i] = sum2[i - 1] + b[i]; 26 } 27 cin >> x; 28 for (int i = 1; i <= n; i++) 29 { 30 for (int j = 0; j < n - i + 1; j++) 31 { 32 min1[i] = min(min1[i], sum1[i + j] - sum1[j]); 33 } 34 } 35 for (int i = 1; i <= m; i++) 36 { 37 for (int j = 0; j < m - i + 1; j++) 38 { 39 min2[i] = min(min2[i], sum2[i + j] - sum2[j]); 40 } 41 } 42 int ans = 0; 43 for (int i = 1; i <= n; i++) 44 { 45 for (int j = 1; j <= m; j++) 46 { 47 if (min1[i] <= x && x / min1[i] >= min2[j]) 48 { 49 ans = max(ans, i * j); 50 } 51 } 52 } 53 cout << ans << endl; 54 } 55 return 0; 56 }