P1387最大正方形前缀和求助
  • 板块灌水区
  • 楼主LYZ0602
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/21 09:21
  • 上次更新2024/7/21 10:57:03
查看原帖
P1387最大正方形前缀和求助
1246191
LYZ0602楼主2024/7/21 09:21
#include<iostream>

using namespace std;

int n ,m;
int Len;
int f[105][105];
int a[105][105];

int calc(int x1 , int y1 , int x2 , int y2) {
	return f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]; 
}

int main()
{
	cin >> n >> m;
	for ( int i = 1 ; i <= n ; i ++) {
		for (int j = 1 ; j <= m ; j ++) {
			cin >> a[i][j];
			f[i][j] = f[i-1][j] + f[j-1][i] - f[i-1][j-1] + a[i][j];
		}
	}
	for (Len = min(n, m) ; Len >= 1 ; Len --) {
		for(int a = Len ; a <= n ; ++ a) {
			for(int b = Len ; b <= m ; ++ b) {
				if(calc(a - Len + 1 , b - Len + 1 , a , b) == Len * Len) {
					cout << Len << endl;
					return 0;
				}
			}
		}
	} 
	return 0;
}

歪解能过,但前缀和没过

2024/7/21 09:21
加载中...