見題：

很水的一題，數據范圍太小，前綴和加爆搜就行.

#include<bits/stdc++.h> using namespace std; const int maxn=110; int ans=1,m,n,sum[maxn][maxn]; inline int read() {int x=0,ff=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*ff; } inline void put(int x) {if(x<0) putchar('-'),x=-x;if(x>9) put(x/10);putchar(x%10+'0'); } int main() {//freopen("1.in","r",stdin);n=read();m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int x=read();sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;}}for(int len=2;len<=min(n,m);len++){int he=len*len;for(int x1=1;x1<=n-len+1;x1++){for(int y1=1;y1<=m-len+1;y1++){int x2=x1+len-1;int y2=y1+len-1;if((sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1])==he) ans=len;}}}put(ans);return 0; }

可是還是想寫正解，DP；

對于這類的二維DP，個人理解就是如果保存的從起點到終點的狀態會被一些情況所中斷，就要只考慮最下角的點所保存的點的狀態，例如此題，我們可以保存以（i,j）為右下角的狀態，以f[i][j]保存以(i,j)為最右下角的最大正方形邊長.狀態轉移怎么樣呢？

這是我們我們可以輕易的想起二維的前綴和：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j],那這個能否用前綴和處理呢，見下圖：

最右下的小矩陣代表（i，j）可以很清楚地看出由左邊的點，上邊的點，左上角的點三個點的最小矩陣構成以個完整的矩陣，即：if(a[i][j]==1) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;

這也提醒我們min的意義就是幾個狀態都具備的共同元素.

#include<bits/stdc++.h> using namespace std; const int maxn=110; int m,n,a[maxn][maxn],f[maxn][maxn],ans; inline int read() {int x=0,ff=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*ff; } int put(int x) {if(x<0) putchar('-'),x=-x;if(x>9) put(x/10);putchar(x%10+'0'); } inline void DP() {for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) {if(a[i][j]==1) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;ans=max(ans,f[i][j]);}} } int main() {freopen("1.in","r",stdin);n=read();m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) a[i][j]=read();}DP();put(ans);return 0; }

?下一題：

這一題就不能用暴力了，（n<=2600,m<=2600）只能想正解，和上一題一樣我們可以用f[i][j]一（i，j）保存合法的吃到的最大的魚的個數.

接下來就考慮狀態怎么轉移，我自己也是嗑了許多時間還沒做出來，于是就看了題解...

給出代碼：

#include<bits/stdc++.h> using namespace std; #define _ 0 const int maxn=2600; int m,n,a[maxn][maxn],f[maxn][maxn],s1[maxn][maxn],s2[maxn][maxn],ans; inline int read() {int x=0,ff=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*ff; } inline void put(int x) {if(x<0) putchar('-'),x=-x;if(x>9) put(x/10);putchar(x%10+'0'); } int main() {freopen("1.in","r",stdin);n=read();m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) a[i][j]=read(); }for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) {if(!a[i][j]) {s1[i][j]=s1[i][j-1]+1;s2[i][j]=s2[i-1][j]+1;}if(a[i][j]){f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;ans=max(ans,f[i][j]);}}}memset(f,0,sizeof(f));memset(s1,0,sizeof(s1));memset(s2,0,sizeof(s2));for(int i=1;i<=n;i++){for(int j=m;j>=1;j--){if(!a[i][j]) {s1[i][j]=s1[i][j+1]+1;s2[i][j]=s2[i-1][j]+1;}if(a[i][j]){f[i][j]=min(f[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1;ans=max(ans,f[i][j]);}}}put(ans);return (0^_^0); }

啟示我們可以直接從最優解的轉移推狀態轉移方程...

轉載于:https://www.cnblogs.com/gcfer/p/10747207.html

總結

以上是生活随笔為你收集整理的最大矩阵（简单DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

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