codeforce D. White Lines

二维前缀和

给你一个n*n的矩阵，里面有两种字符，‘W’和‘B’，代表black 和white 。其实这个矩阵就是一个方形画板，你有一个k*k的橡皮只能用一次，使k*k的矩阵里的B变成W，问完全空白的行和列的总数？

思路：

用1代替B，0代替W，然后维护一个前缀和数组，看能否用一个橡皮的操作使这一列或行的前缀和变为0，然后维护答案就好了，具体操作可以把列对称成行，相当于搞两个不同的数组，这样就只需要搞两个数组的行就可以了。如图：

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2010;
 4 int n,k,ans,tot,r[N][N],c[N][N],okr[N][N],okc[N][N];
 5 char mp[N][N];
 6 int main()
 7 {
 8     scanf("%d%d%*c",&n,&k);
 9     for(int i=1;i<=n;scanf("%*c"),i++)
10         for(int j=1;j<=n;j++)
11             scanf("%c",&mp[i][j]);
12 //  输入 
13     for(int i=1;i<=n;i++)
14         for(int j=1;j<=n;j++)
15             r[i][j]=r[i][j-1]+(mp[i][j]=='B'),c[i][j]=c[i][j-1]+(mp[j][i]=='B');
16 //  记录 1代表'B'，0代表'W';
17 //  这里将数组关于斜对角线对称一下，问题就变成了统计对称前擦除操作后有多少个全0的行！
18 //  和对称后的那个数组擦除操作后有多少的全0的行（因为对称后列变成了行）如上图 
19     for(int i=1;i<=n;i++)tot+=(r[i][n]==0)+(c[i][n]==0);
20 // tot是没有擦除操作就是全0行的个数 
21     for(int i=1;i<=n;i++)
22         for(int j=1;j<=n-k+1;j++)
23             okr[i][j]=(r[i][j+k-1]-r[i][j-1]==r[i][n]&&r[i][n]!=0)+okr[i-1][j],
24             //这一行中只有长度为k的区间有1等价于【(r[i][j+k-1]-r[i][j-1]==r[i][n]】
25             // 【r[i][n]!=0】避免重复计算初始为全0行的个数 
26             //那么可以通过擦除操作对答案做出贡献 ，并作一个前缀和 
27             okc[i][j]=(c[i][j+k-1]-c[i][j-1]==c[i][n]&&c[i][n]!=0)+okc[i-1][j];
28             //同理 
29     for(int i=1;i<=n-k+1;i++)
30         for(int j=1;j<=n-k+1;j++)
31             ans=max(ans,tot+okr[i+k-1][j]-okr[i-1][j]+okc[j+k-1][i]-okc[j-1][i]);
32             //维护一个初始全0行+操作后对答案贡献的两个区间和  
33     printf("%d",ans);
34 }