算法竞赛AcWing在线题库_4395. 最大子矩阵

#include<iostream>  

#include<algorithm>

 using namespace std;

 /* 

 (a[i]+ a[i+1]+...+a[j])(b[s]+ b[s+1]+...+b[t])<=x

 求 (j - i + 1)*(t - s + 1) 最大

 */

const int N = 2010;

int n=3, m=3, x=9;

int a[N]={0,1,2,3};

int b[N]={0,1,2,3};

int c[N * N];

int main() {

 /*

cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];

    for (int i = 1; i <= m; i++) cin >> b[i], b[i] += b[i - 1];

    cin >> x; 

*/

  

for (int i = 1; i <= n; i++)    a[i] += a[i - 1];

    for (int i = 1; i <= m; i++)   b[i] += b[i - 1];

    // 数组c[tar]，表示和不超过tar子区间的最大长度

    for (int i = 1; i <= m; i++)

        for (int j = i; j <= m; j++)           

{ if (c[b[j] - b[i - 1]]<j - i + 1)c[b[j] - b[i - 1]]=j - i + 1;

cout<<b[j] - b[i - 1]<<"  "<<j - i + 1<<endl;

}

    for (int i = 1; i < N * m; i++) if (c[i]< c[i - 1])c[i]= c[i - 1];

        

cout << endl;

for (int i = 1; i <n * m; i++) cout<<c[i]<<"  "<<i<<endl;

cout << endl;

    int res = 0;

    for (int i = 1; i <= n; i++)

        for (int j = i; j <= n; j++) {

            int tar = x / (a[j] - a[i - 1]); 

cout<<tar<<"  "<<j - i + 1<<endl;

if (tar >= N * m) { if(res<(j - i + 1) * m)res= (j - i + 1) * m; }

            else 

if(res< c[tar] * (j - i + 1))res= c[tar] * (j - i + 1);

        }

    cout << res<<endl;

}