正題

題目鏈接:https://www.luogu.org/problemnew/show/P3100

---

題目大意

一個空矩陣，每次可以將$B?B$的矩陣覆蓋為$R$或者$B$。

求$B$最大是多少使得可以覆蓋使得原矩陣成為目標矩陣。

---

解題思路

我們考慮貪心，先分析一下性質。

假設答案為$k$，那么目標矩陣上必然有一個邊長為$k$的同顏色正方形。當然考慮最優，我們會讓$k$越大越好。

我們可以每次尋找一個同顏色的最大正方形，然后每次將這個正方形全都覆蓋為兩種顏色通用，直到所有的都被覆蓋，每次取這個最大正方形的最小邊長。

這時就有問題了，我們如何用$dp$計算時保證這個正方形內必定有沒有被覆蓋的情況呢$?$其實我們可以用一個$v_{i,j}$表示以$v$為右下角的最大矩陣是否覆蓋，這樣我們保證每次都找沒有覆蓋的情況就好了。

但是這是我們發現單單這樣會$TLE$，那我們只有限制一下運行次數就可以了，因為若到后面，基本發現不了更小的正方形。

---

$code$

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int n,m,f[110][110],x,y,ans,sum; int a[110][110],k,g[110][110]; bool v[110][110]; void get_ans() {sum=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;g[i][j]=min(g[i-1][j-1],min(g[i-1][j],g[i][j-1]))+1;if(a[i][j]==0) f[i][j]=0;if(a[i][j]==1) g[i][j]=0;if(v[i][j]||max(f[i][j],g[i][j])<=sum) continue;sum=max(f[i][j],g[i][j]);x=i;y=j;}v[x][y]=1;ans=min(ans,sum);for(int i=0;i<sum;i++)for(int j=0;j<sum;j++){if(a[x-i][y-j]!=3) k--;a[x-i][y-j]=3;} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){char x;cin>>x;a[i][j]=(x=='R');}k=n*m;ans=n;for(int i=1;i<=5000&&k;i++) get_ans();printf("%d",ans); }

總結

以上是生活随笔為你收集整理的P3100-[USACO14JAN]建造滑雪场【贪心,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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