现在最常用网站开发工具,中国成熟iphone,网站按条件显示广告图片,马鞍山 做网站CODEVS1159最大全0子矩阵 题目描述 Description 在一个0,1方阵中找出其中最大的全0子矩阵#xff0c;所谓最大是指O的个数最多。思路#xff1a;这个题最朴素的n^6的算法#xff0c;超时美美的。。。然后想优化#xff0c;从一个点向上方、左方、右方扩展#xff0c;首先更…CODEVS1159最大全0子矩阵 题目描述 Description 在一个0,1方阵中找出其中最大的全0子矩阵所谓最大是指O的个数最多。思路这个题最朴素的n^6的算法超时美美的。。。然后想优化从一个点向上方、左方、右方扩展首先更新这个点向上能有多少个0h0然后找左右h比h0大的作为左右边界然后计算这个矩形的面积最后输出最大值。。。这种构造的美丽算法真心。。。比较 最大全0子正方形f[i][j](以ij为右下角的最大正方形的边长)minf[i-1][j],f[i][j-1],f[i-1][j-1],这里用了正方形的特性所以和矩形的求法不同。这属于dp中的重要分支最大子图形问题详细的讲解可以参考下面的网址。。。真心丧病。。。 http://www.docin.com/p-46970779.html code#includeiostream#includecstdiousing namespace std;int li[2001]{0},ri[2001]{0},hi[2001]{0},a[2001][2001]{0};int main(){int n,i,j,ans0;scanf(%d,n);for (i1;in;i)for (j1;jn;j)scanf(%d,a[i][j]);for (i1;in;i){for (j1;jn;j){if (a[i][j]0) hi[j];else hi[j]0;li[j]ri[j]j;}for (j2;jn;j)if (a[i][j]0)while (hi[li[j]-1]hi[j])li[j]li[li[j]-1];for (jn-1;j1;--j)if (a[i][j]0)while (hi[ri[j]1]hi[j])ri[j]ri[ri[j]1];for (j1;jn;j)if (a[i][j]0)ansmax(ans,(ri[j]-li[j]1)*hi[j]);}coutansendl;} RZUC Code CODEVS1259最大正方形子矩阵 题目描述 Description 在一个01矩阵中包含有很多的正方形子矩阵现在要求出这个01矩阵中最大的正方形子矩阵使得这个正方形子矩阵中的某一条对角线上的值全是1其余的全是0。 思路做了好几个有关的最大子阵的问题发现还是有些困难做这个题想了好久发现其实很简单利用全0子矩阵的思路和正方形的思路就可以比较简单的写出dp方程。预处理一个点上方hi左方li和右方ri0的个数不包含这个点本身。 f[i][j]min(f[i-1][j-1]1,min(li[i][j]1,hi[i][j]1)) 第一个比较容易错的地方就来每次对于能更新的f[i][j]的位置要求在map中为1否则就不能构成要求的正方形 其次就是题目中要求对角线为1一个正方形有两条对角线都应该考虑到根据f数组的更新可以同理写出 在预处理的时候细心注意这个点和周围点的关系就可以了。 #includeiostream
#includecstdio
using namespace std;
int map[1010][1010]{0},li[1010][1010]{0},ri[1010][1010]{0},hi[1010][1010]{0},f[1010][1010]{0},g[1010][1010]{0};
int main()
{int n,m,i,j,ans0;cinnm;for (i1;in;i){for (j1;jm;j){scanf(%d,map[i][j]);hi[i][j]hi[i-1][j];li[i][j]li[i][j-1];if (map[i-1][j]0) hi[i][j];else hi[i][j]0;if (map[i][j-1]0j1) li[i][j];else li[i][j]0; }for (jm-1;j1;--j){ri[i][j]ri[i][j1];if (map[i][j1]0) ri[i][j];else ri[i][j]0;}}for (i1;in;i){for (j1;jm;j)if (map[i][j]1){f[i][j]min(f[i-1][j-1]1,min(li[i][j]1,hi[i][j]1));if (f[i][j]ans) ansf[i][j];}for (jm;j1;--j)if (map[i][j]1){g[i][j]min(g[i-1][j1]1,min(ri[i][j]1,hi[i][j]1));if (g[i][j]ans)ansg[i][j];}}coutansendl;
} RZUC Code 从网上看到了一个很全的子图形问题的Word分享一下http://www.docin.com/p-351795539.html tyvj1563最大正方形 思路这个题目很特殊要求最大正方形中相邻两点的颜色不同所以可以读图的时候进行处理隔一个变一次使这个位置上0、1互换这样就转化成了矩阵中的最大全0或全1子正方形了非常简单的dp解决 f[i][j]min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))1;(全0先判断map[i][j]0) 全1同理 最大子图形问题的众多变式都应能转化为基本的求正方形、矩形等问题得以比较简单的解决。看来noip后要找时间好好研究了。。。 bzoj1057 棋盘制作 题目大意求一个01交错的最大正方形和矩形面积。 思路把ij%20的位置0/1互换一下就变成了求最大0/1子矩阵问题正方形可以根据长宽中取较小作为边长就可以了。 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#define maxnode 2005
using namespace std;
int map[maxnode][maxnode]{0},hi[maxnode]{0},li[maxnode]{0},ri[maxnode]{0};
int fang(int x){return x*x;}
int main()
{int i,j,ans10,ans20,k,n,m;scanf(%d%d,n,m);for (i1;in;i)for (j1;jm;j){scanf(%d,map[i][j]);if ((ij)%2) map[i][j]^1;}for (k0;k1;k){memset(hi,0,sizeof(hi));for (i1;in;i){for (j1;jm;j){if (map[i][j]k) hi[j];else hi[j]0;li[j]ri[j]j;if (j1map[i][j]k)while(hi[li[j]-1]hi[j]) li[j]li[li[j]-1];}for (jm-1;j1;--j)if (map[i][j]k)while(hi[ri[j]1]hi[j]) ri[j]ri[ri[j]1];for (j1;jm;j)if (map[i][j]k){ans1max(ans1,fang(min(hi[j],ri[j]-li[j]1)));ans2max(ans2,hi[j]*(ri[j]-li[j]1));}}}printf(%d\n%d\n,ans1,ans2);
} View Code 转载于:https://www.cnblogs.com/Rivendell/p/4076516.html
