萌新求助站外题(玄关1个&急
  • 板块灌水区
  • 楼主BK小鹿
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/19 11:25
  • 上次更新2024/5/19 13:58:20
查看原帖
萌新求助站外题(玄关1个&急
1345783
BK小鹿楼主2024/5/19 11:25

rt,题目:

1

WA Code

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1005;

int n, m;
int a[N][N], h[N][N], r[N][N], l[N][N], sum[N][N];
int res = -1;

void read()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ )
	  for (int j = 1; j <= m; j ++ )
	    scanf("%d", &a[i][j]);
    
    for (int i = 1; i <= n; i ++ )
      for (int j = 1; j <= m; j ++ )
        sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    
    for (int i = 1; i <= n; i ++ )
    {
      for (int j = 1; j <= m; j ++ )
      	if (!a[i][j]) h[i][j] = r[i][j] = l[i][j] = 0;
      	else h[i][j] = h[i - 1][j] + 1, l[i][j] = l[i][j - 1] + 1;
      for (int j = m; j >= 1; j -- )
        if (!a[i][j]) r[i][j] = 0;
        else r[i][j] = r[i][j + 1] + 1;
    }	
}

void dp()
{
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
			if (h[i][j] > 0)
			{
				if (h[i][j] > 1)  l[i][j] = min(l[i][j], l[i - 1][j]), r[i][j] = min(r[i - 1][j], r[i][j]);
				int x2 = i, y2 = j + r[i][j] - 1, x1 = i - h[i][j] + 1, y1 = j - l[i][j] + 1;
				int cnt = sum[x2][y2] - sum[x2][y1 - 1] - a[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
				res = max(res, cnt);
			}
	printf("%d\n", res);
}

int main()
{
	read(); 
    dp();
    return 0;
}
2024/5/19 11:25
加载中...