dp + 前缀和 全wa
查看原帖
dp + 前缀和 全wa
575423
Coding_Zhouzehao楼主2022/5/13 22:20
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 410;
int s[MAXN][MAXN];
int temp[MAXN];
int f[MAXN];
int ans = -0x7fffffff;
int n, m, t;
void solve()
{
	memset(f, 0, sizeof(f));
	for (int i = 1; i <= m; i++)
	{
		f[i] = max(f[i], f[i - 1] + temp[i]);
		ans = max(ans, f[i]);
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= n;i++)
		for (int j = 1; j <= m; j++)
		{
			char t;
			scanf("%c", &t);
			s[i][j] = s[i - 1][j];
			if (t == '1')
				++s[i][j];
			else
				--s[i][j];
		}
	for(int i = 1;i <= n;i++)
		for (int k = 1; k <= i; k++)
		{
			for (int j = 1; j <= m; j++)
			{
				temp[j] = s[i][j] - s[i - k][j];//直接求得行的前缀和 
			}
			solve();
		}
	cout << ans;
	return 0;
}
2022/5/13 22:20
加载中...