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 }