怎样创建网站dw,网络营销代运营服务,推销网站话术,邮件模板网站Em...属于一知道就会#xff0c;不知道的话比较难想。
我们先看题#xff1a; 我们不妨把1抽象成一个平面上的点#xff0c;因此可以变成这一幅图#xff1a; 我们假设每一个点被向上牵拉了一根线#xff1a; 显然#xff0c;每一条悬线都有可能成为边界限制#xff0c…Em...属于一知道就会不知道的话比较难想。
我们先看题 我们不妨把1抽象成一个平面上的点因此可以变成这一幅图 我们假设每一个点被向上牵拉了一根线 显然每一条悬线都有可能成为边界限制我们确定一条悬线乘上悬线最左可到的最右可到的距离即可。
首先对于上下边界的悬线我们记h[i][j]为(i,j)的悬线长度易得方程
h[i][j]h[i-1][j]1(a[i][j]0)或者0(a[i][j]1).
我们再维护向左的长度。
我们记l[i][j]表示向左最远.l[i][j]l[i][j-1]1(a[i][j]0)/0(a[i][j]1)
我们记L[i][j]表示i,j)这条悬线向左最远。
L[i][j]min(L[i-1][j],l[i][j]).
向右同理。
下面是AC代码
#includebits/stdc.h
using namespace std;
int l[100][100],r[100][100],h[100][100],n,a[90][90];
int main(){cinn;int ans0;for(int i1;in;i){for(int j1;jn;j){cina[i][j];}}for(int i1;in;i){for(int j1;jn;j){if(a[i][j]1){h[i][j]0;l[i][j]0;}else{h[i][j]h[i-1][j]1;l[i][j]l[i][j-1]1;}}for(int jn;j1;j--){if(a[i][j]1){r[i][j]0;}else r[i][j]r[i][j1]1;}}for(int i1;in;i){for(int j1;jn;j){if(h[i][j]2){//注意为2若为1时会把上面的0带下来而事实上1的值不用改l[i][j]min(l[i][j],l[i-1][j]);r[i][j]min(r[i][j],r[i-1][j]);}ansmax(ans,(r[i][j]l[i][j]-1)*h[i][j]);}}coutans;
}
那么如果要求是正方形呢
很简单我们只要把h[i][j]与r[i][j]l[i][j]-1取min并平方即可。
我们来看一个变形题吧 这里有两种方法
1.我们还是用悬线只不过转移条件需要修改与自己颜色不同时转移
2.我们先进行染色操作我们按照国际象棋去染色我们把国际象棋为1的位置进行颠倒。1变成00变成1我们再求其中的全0/1最大子矩形即可我们反着看把全0/1的恢复一下不就是了吗
下面给出法2的AC代码
#includebits/stdc.h
using namespace std;
int l[2010][2010],r[2010][2010],h[2100][2010],n,m,a[2010][2010];
int l1[2010][2010],r1[2010][2010],h1[2100][2010];
int main(){cinnm;int ans00,ans10,ans000,ans110;for(int i1;in;i){for(int j1;jm;j){scanf(%d,a[i][j]);}}int cnt1;for(int i1;in;i){for(int j1;jm;j){if(j%2cnt) a[i][j]1-a[i][j];}cnt1-cnt;}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]1){h[i][j]0;l[i][j]0;}else{h[i][j]h[i-1][j]1;l[i][j]l[i][j-1]1;}}for(int jm;j1;j--){if(a[i][j]1){r[i][j]0;}else r[i][j]r[i][j1]1;}}for(int i1;in;i){for(int j1;jm;j){if(h[i][j]2){l[i][j]min(l[i][j],l[i-1][j]);r[i][j]min(r[i][j],r[i-1][j]);}ans0max(ans0,(r[i][j]l[i][j]-1)*h[i][j]);ans00max(ans00,min(r[i][j]l[i][j]-1,h[i][j])*min(r[i][j]l[i][j]-1,h[i][j]));}}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]0){h1[i][j]0;l1[i][j]0;}else{h1[i][j]h1[i-1][j]1;l1[i][j]l1[i][j-1]1;}}for(int jm;j1;j--){if(a[i][j]0){r1[i][j]0;}else r1[i][j]r1[i][j1]1;}}for(int i1;in;i){for(int j1;jm;j){if(h1[i][j]2){l1[i][j]min(l1[i][j],l1[i-1][j]);r1[i][j]min(r1[i][j],r1[i-1][j]);}ans1max(ans1,(r1[i][j]l1[i][j]-1)*h1[i][j]);ans11max(ans11,min(r1[i][j]l1[i][j]-1,h1[i][j])*min(r1[i][j]l1[i][j]-1,h1[i][j]));}}coutmax(ans00,ans11)endl;coutmax(ans0,ans1);
}
