正題

題目鏈接:https://www.luogu.org/problem/CF1200D

---

題目大意

一個黑白組成的$n?n$矩陣，然后可以選擇將$k?k$的覆蓋為白色，然后求有多少白線(整行或整列都是白色)。

---

解題思路

對于每一行或每一列可以變成白線的話那么可行范圍一定是一個矩陣，我們用二維前綴和，每次讓整個可以產生貢獻的矩陣都$+1$，然后求值最大的位置即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2100; int n,k,ans[N][N],maxs,cl; char s[N][N]; void addw(int x1,int y1,int x2,int y2) {x1=max(x1,1);y1=max(y1,1);x2=max(x2,1);y2=max(y2,1);//printf("%d,%d,%d,%d\n",x1,y1,x2,y2);ans[x1][y1]++;ans[x1][y2+1]--;ans[x2+1][y2+1]++;ans[x2+1][y1]--; } int main() {scanf("%d%d\n",&n,&k);for(int i=1;i<=n;i++)gets(s[i]+1);for(int i=1;i<=n;i++){int mx=0,mi=n+1;for(int j=1;j<=n;j++)if(s[i][j]=='B') mx=max(mx,j),mi=min(mi,j);if(!mx) {cl++;continue;}if(mx-mi+1>k) continue;addw(mx-k+1,i-k+1,mi,i);}for(int i=1;i<=n;i++){int mx=0,mi=n+1;for(int j=1;j<=n;j++)if(s[j][i]=='B') mx=max(mx,j),mi=min(mi,j);if(!mx) {cl++;continue;}if(mx-mi+1>k) continue;addw(i-k+1,mx-k+1,i,mi);}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]+=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];for(int i=1;i<=n-k+1;i++)for(int j=1;j<=n-k+1;j++)maxs=max(maxs,ans[i][j]);printf("%d",maxs+cl); }

總結

以上是生活随笔為你收集整理的CF1200D-White Lines【二维前缀和】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。