线代高手_牛客博客

链接：https://ac.nowcoder.com/acm/contest/63602/J
来源：牛客网

题目描述

小H是大家公认的线代高手，他最近遇到了一个题，题意如下：给定长度为nnn的数组AAA和长度为mmm的数组BBB。

定义一个n∗mn*mn∗m的矩阵CCC, 其中Ci,jC_{i,j}Ci,j为 Ai∗BjA_i*B_jAi∗Bj ,(注意矩阵CCC不会直接给出) ，同时给出一个整数xxx, 你需要找到矩阵CCC的一个子矩阵，满足该子矩阵元素和小于等于xxx, 同时让该子矩阵的面积尽可能大。求出该子矩阵的最大面积。

作为线代高手的小H很快就算出了答案，那么你知道答案是多少吗？

输入描述:

第一行输入两个整数nnn和mmm,分别表示数组AAA和数组BBB的长度。
第二行输入nnn个整数，表示数组AAA的元素。
第三行输入mmm个整数，表示数组BBB的元素。
	
		第四行输入一个整数xxx, 即为题目中要求的xxx。
	

	
		1≤n,m≤501 \leq n,m \leq 501≤n,m≤50, 1≤Ai,Bi≤501 \leq A_i,B_i \leq 501≤Ai,Bi≤50 , 1≤x≤1051 \leq x \leq 10^51≤x≤105.

输出描述:

输出一个整数 ,表示满足条件的子矩阵的最大面积。

示例1

输入

复制 3 3 1 2 4 1 2 4 9

输出

复制 4

说明

	
		CCC矩阵为：
	

	
		1 2 4
	

	
		2 4 8
	

	
		4 8 16
	

	
		元素和小于等于9的面积最大的子矩阵就是左上角2*2的矩阵，所以答案是4。

本题给的数据范围较小，所以可以稍微暴力解法。用i和j去控制矩形的的形状范围，然后使用is_ok函数去判断当前区域里面的点和是否符合题目中的要求。最后将所有的小矩形遍历完成之后取最大值即可，注意仍需要使用二维数组前缀和来快速获取区域里面的和。

AC代码：

#include <bits/stdc++.h>

using namespace std;

int A[55];
int B[55];
int c[55][55];
int n, m, x;
bool is_ok(int i, int j) {
    for (int x1 = 1;x1+i-1<=n;x1++) {
        for (int y1 = 1;y1+j-1<=m;y1++) {
            int x2 = x1+i-1, y2 = y1+j-1;
            if (c[x2][y2]-c[x1-1][y2]-c[x2][y1-1]+c[x1-1][y1-1]<=x) {
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>A[i];
    }
    for (int i=1;i<=m;i++) {
        cin>>B[i];
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            c[i][j] = A[i]*B[j];
            c[i][j] += c[i-1][j]+c[i][j-1]-c[i-1][j-1];
        }
    }
    int ans = -1;
    cin>>x;
    for (int i=n;i>0;i--) {
        for (int j=m;j>0;j--) {
            if (is_ok(i, j)) {
                if (i*j>ans) {
                    ans = i*j;
                }
            }
        }
    }
    cout<<ans;
    
    return 0;
}