打卡信奥刷题（3156）用C++实现信奥题 P7741 [AHOI2007] 石块地板

P7741 [AHOI2007] 石块地板

题目描述

小可可来到了宫殿的正厅中。大厅的地面是由一块块大小一致的正方形石块组成的，这些石块分为黑、白两色，组成了一个m×nm×nm×n的矩形，在其中一个石块的下面就是通往藏宝库的通道。小可可不可能一个一个石块的尝试，因为有些石块安装了机关，一碰就会触发，整个宫殿也随之倒塌。根据藏宝图记载，通道在某一特定的区域中，这个区域是一个由数个石块组成的面积不为000的小矩形，它的四条边与大厅地面的边平行。如果对整个大厅地面任意划分矩形，那么在所有矩形中，这个区域的黑色石块数目减去白色石块数目所得的差是最大的。

小可可希望和你分工，由他来选择区域，你来计算黑、白两色石块的数目差SSS。这样就能快速而准确的确认通道所在的区域。藏宝图上说这个区域中的石块都没有安装机关，只要确定了区域，就一定能找到通道。宝藏就在眼前了，加油吧！

（假设用111表示黑色石块，用000表示白色石块）

输入格式

输入文件的第一行为两个整数m,nm,nm,n。

以下mmm行，每行nnn个字符，每个字符都是000或111。

输出格式

输出文件仅一个数，表示所有可能的区域中SSS值（见前文描述）最大的一个，输出这个值即可。

输入输出样例 #1

输入 #1

3 4 1011 1111 1111

输出 #1

10

输入输出样例 #2

输入 #2

4 5 10110 01111 11110 10101

输出 #2

8

说明/提示

对于 $ 50%$ 的数据：1≤m,n≤2001 \le m, n \leq2001≤m,n≤200。

对于100%100\%100%的数据：1≤m,n≤4001 \le m, n \leq4001≤m,n≤400。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definemaxn405intm,n,ans;intsum[maxn][maxn],f[maxn];charc;signedmain(){cin>>m>>n;//注意不是 n 行 m 列for(inti=1;i<=m;i++)for(intj=1;j<=n;j++){cin>>c;if(c=='1')sum[i][j]=sum[i][j-1]+1;elseif(c=='0')sum[i][j]=sum[i][j-1]-1;}//求出每一行的前 j 个数的前缀和for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){//枚举第 i 列到第 j 列for(intk=1;k<=m;k++)f[k]=sum[k][j]-sum[k][i-1];//把每一行的和算出来for(intk=1;k<=m;k++){f[k]=max(f[k],f[k]+f[k-1]);ans=max(ans,f[k]);}//最大子段和问题}cout<<ans<<endl;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容