网络游戏网站开发,吉林市网页设计,天天清茶 湖南网站建设,在招聘网站做销售工资高吗一.矩形的最大面积——单调栈
#xff08;1#xff09;例题
P4147 玉蟾宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#xff08;2#xff09;讲解#xff08;摘自题解#xff09;
问题转化#xff1a; n行m列土地#xff0c;求最大矩形面积#xff0c;我们把…一.矩形的最大面积——单调栈
1例题
P4147 玉蟾宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
2讲解摘自题解
问题转化 n行m列土地求最大矩形面积我们把问题拆分成n个子问题来解决. 对于每一行,依次记录每行向上一直是F土地的可延伸的最大距离记为f(i,j). 当前元素(i,j)为F,则f(i,j)f(i-1,j)1.当前元素(i,j)为R,则f(i,j)0. 我们记录这个数组有什么用呢这就可以转化为单调栈维护的问题了.
具体思路 对于每一个子问题我们维护一个单调递增的单调栈.我们定义一个结构体(其中记录的两个元素分别是当前行第j个矩形的f值以及它在当前已加入栈中矩形高度的排名). 我们考虑当前加入第k个矩形的情况. 当前矩形高度大于栈顶直接加入即可因为没有比它大的元素那么他的排名为1. 当前矩形高度小于栈顶则不断取出栈顶直到栈为空或者栈顶矩形的高度比当前矩形小.在出栈过程中我们累计被弹出的矩形的宽度之和并且每弹出一个矩形就用它的高度乘上累计的排名是累计因为在它入栈后还有比它大的元素入栈来更新答案. 这样为什么是对的呢这是因为如果当前要加入矩形的f值即当前矩形的高度比上一个小那么该矩形想利用前面的矩形一起构成一个大矩形是这块矩形的高度不可能超过该矩形自己的高度则记录前面元素的高度就没有用处了.而宽度还有用处因为当前矩形高度较小与比它高的矩形的宽度总和相乘在此矩形出栈时要用它来更新答案.所以我们要记一个当前已加矩形的高度排名无论是在栈里还是已经出栈.而又因为每个元素只被弹栈一次所以不会有重复情况. 在所有矩形m个都考虑过后我们再用还没有弹栈的元素再来个新一波答案直到栈空
3AC
#includebits/stdc.h
#define maxn 1005
using namespace std;
int n,m;
int ans,maxs;
struct node{int hign,length;
}sta[maxn];
int f[maxn][maxn]; //记录每行每列的高
void work(int x){int top1,len0;maxs0;sta[top].hignf[x][1];sta[top].length1;for(int i2;im;i){len0;//维持递增 while(sta[top].hignf[x][i] top0){lensta[top].length; //继承长度毕竟高的可以低的也必可以 maxsmax(maxs,sta[top--].hign*len);}sta[top].hignf[x][i];sta[top].lengthlen1;}len0;//同上while while(top){lensta[top].length; maxsmax(maxs,sta[top--].hign*len);}ansmax(ans,maxs);
}
int main(){scanf(%d%d,n,m);char c;for(int i1;in;i){for(int j1;jm;j){cinc;if(cF) f[i][j]f[i-1][j]1;}}//枚举每一行解决子问题 for(int i1;in;i) work(i);printf(%d,ans*3);return 0;
} 二.正方形的最大面积——dp
1例题
P1387 最大正方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
2讲解
就是一个简单的dpdp状态转移方程式为
dp[i][j]min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])1;
3AC
#includebits/stdc.h
#define maxn 101
using namespace std;
int n,m;
int a[maxn][maxn],dp[maxn][maxn];
int ans;
int main(){cinnm;for(int i1;in;i)for(int j1;jm;j)scanf(%d,a[i][j]);for(int i1;in;i){for(int j1;jm;j){if(a[i][j]1){dp[i][j]min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])1; }ansmax(ans,dp[i][j]);}} coutans;}
