UVA-10074 最大子矩阵 DP
求出大矩阵里面全为0的最大子矩阵
我自己用的个挫DP写的，感觉写的不是很好，其实可以再优化，DP想法就是以 0 0 到当前 i j 为整体矩阵考虑，当前 i j就是从 i-1 j或者 i，j-1那里最大化，然后因为要求最大子矩阵，还得自从j往上扫一遍。。总之好像有点挫
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int dp[105][105][2]; int s[105][105]; int g[105][105]; int n,m,i,j,k; int main() { while (scanf("%d%d",&n,&m)) { if (n==0 && m==0) break; for (i=1;i<=n;i++) { for (j=1;j<=m;j++) { scanf("%d",&g[i][j]); s[i][j]=dp[i][j][0]=dp[i][j][1]=1-g[i][j]; } } int ans=0; for (i=1;i<=n;i++) { for(j=1;j<=m;j++) { if (j-1>=1 && !g[i][j] && !g[i][j-1]) { dp[i][j][0]=max(dp[i][j-1][0]+1,dp[i][j][0]); s[i][j]=max(s[i][j],dp[i][j][0]); } if (i-1>=1 && !g[i][j] && !g[i-1][j]) { dp[i][j][1]=max(dp[i-1][j][1]+1,dp[i][j][1]); s[i][j]=max(s[i][j],dp[i][j][1]); int temp=dp[i][j][1]; temp--; int cur=dp[i][j][0]; for (k=i-1;k>=1 && temp;k--,temp--) { cur=min(dp[k][j][0],cur); s[i][j]=max(s[i][j],cur*(i-k+1)); } } ans=max(ans,s[i][j]); } } printf("%d ",ans); } return 0; }