给千图网等网站做设计赚钱吗,北京建设银行分行招聘网站,如何制作手机网页最简单的方法,porto wordpress汉化版/*
1017: C03-单调栈算法-最大长方形时间限制: 1 Sec 内存限制: 128 MB
提交: 17 解决: 10
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述给你一个直方图#xff0c;告诉你各个条形矩形的高度#xff0c;求基线对齐构成的矩形中面积最大的矩形的面积。对于每一个矩形… /*
1017: C03-单调栈算法-最大长方形时间限制: 1 Sec 内存限制: 128 MB
提交: 17 解决: 10
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述给你一个直方图告诉你各个条形矩形的高度求基线对齐构成的矩形中面积最大的矩形的面积。对于每一个矩形面积 h[i]*(j-k1),其中jk是左右边界h[i]是矩形的高。并且对于j x kh[i] h[x]。代码提交链接输入
输入包含几个测试用例。每个测试用例描述一个直方图并以整数n开始表示它由多少个矩形组成。你可以假设1 n 100000。然后按照n个整数h1… hn其中0 hi 1000000000。这些数字表示直方图中从左到右排列的矩形的高度。每个矩形的宽度是1。0紧跟最后一个测试用例的输入。输出
对于单个行上的每个测试用例输出指定直方图中最大矩形的面积。记住这个矩形必须与公共基线对齐。样例输入7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0样例输出8
4000提示我们可以用一个单调栈由低到高来存储它的高度并用数组对每个高度记录一下它前面包括它自己一共有多少个比它高的可以看做它的左宽。
按顺序考虑每个高度h如果h大于栈顶元素则入栈此时它大于左面全部的元素并且将它的宽度初始为1。
否则将栈内元素出栈直到满足上面的条件。出栈时我们要将出栈元素对之后问题的影响全部考虑进行处理才能保证做法的正确性。
对于每个高度它的作用无非两个1、以自己作高向外扩展 2、以别人作高自己被扩展
由于我们数组中已经记录了某个高度的左宽所以我们只需要考虑它能不能向右扩展如果能能扩展多少
首先对于第一个出栈的元素来说它的右宽一定是0。
然而对于第二个它的右边有刚才出栈的元素而且刚才出栈元素的总宽中所涉及的元素一定可以被自己扩展所以自己的右宽为刚才出栈元素的总宽。
同理可知第三个出栈元素的右宽为第二个出栈元素的总宽。依次类推。
而当h大于栈顶元素时h的左宽应该是上次出栈元素的总宽1自己然后入栈。
最后时将所有元素出栈即可将所有情况考虑。来源/分类
C03-栈 [提交] [状态]*/
#includeiostream
#includecstdio
#includealgorithm
#includecmath
#includestring
#includecstring
#includestack
using namespace std;
const int Max_N100008;
struct Elem{int id;//向左扩展最远的下标 long long height;//当前节点高度 Elem(){} //在其他的地方要定义一个Elem类型的变量的时候一定要加 Elem(int _id,long long _height):id(_id),height(_height){}
};
int N;
long long x[Max_N];
long long Ans(){int i,L_id;long long ans0;Elem e;stackElem stk;for(i0;iN;i){L_idi;while(!stk.empty()stk.top().heightx[i]){ansmax(ans,(long long)(i-stk.top().id)*stk.top().height);L_idstk.top().id;stk.pop();}//由于上面修改了L_id这里相当于每次加入一个长度为(i-L_id)的长方形//这里枚举一遍找一个最大值就可以了 stk.push(Elem(L_id,x[i]));}return ans;
}int main()
{int i;while(cinNN){for(int i0;iN;i)scanf(%lld,x[i]);x[N]-1;coutAns()endl;}return 0;
}/**************************************************************Problem: 1105User: BlingoLanguage: CResult: 正确Time:36 msMemory:2880 kb
****************************************************************/ 1105: B10-动态规划直方图最大长方形 时间限制: 1 Sec 内存限制: 128 MB提交: 8 解决: 5[提交] [状态] [讨论版] [命题人:外部导入] 题目描述 给你一个直方图告诉你各个条形矩形的高度求基线对齐构成的矩形中面积最大的矩形的面积。对于每一个矩形面积 h[i]*(j-k1),其中jk是左右边界h[i]是矩形 的高。并且对于j x kh[i] h[x]。 输入 输入包含几个测试用例。每个测试用例描述一个直方图并以整数n开始表示它由多少个矩形组成。你可以假设1 n 100000。然后按照n个整数h1… hn其中0 hi 1000000000。这些数字表示直方图中从左到右排列的矩形的高度。每个矩形的宽度是1。0紧跟最后一个测试用例的输入。 输出 对于单个行上的每个测试用例输出指定直方图中最大矩形的面积。记住这个矩形必须与公共基线对齐。 样例输入 7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0 样例输出 8
4000 提示 我们可以用一个单调栈由低到高来存储它的高度并用数组对每个高度记录一下它前面包括它自己一共有多少个比它高的可以看做它的左宽。按顺序考虑每个高度h如果h大于栈顶元素则入栈此时它大于左面全部的元素并且将它的宽度初始为1。否则将栈内元素出栈直到满足上面的条件。出栈时我们要将出栈元素对之后问题的影响全部考虑进行处理才能保证做法的正确性。对于每个高度它的作用无非两个1、以自己作高向外扩展 2、以别人作高自己被扩展由于我们数组中已经记录了某个高度的左宽所以我们只需要考虑它能不能向右扩展如果能能扩展多少首先对于第一个出栈的元素来说它的右宽一定是0。然而对于第二个它的右边有刚才出栈的元素而且刚才出栈元素的总宽中所涉及的元素一定可以被自己扩展所以自己的右宽为刚才出栈元素的总宽。同理可知第三个出栈元素的右宽为第二个出栈元素的总宽。依次类推。而当h大于栈顶元素时h的左宽应该是上次出栈元素的总宽1自己然后入栈。最后时将所有元素出栈即可将所有情况考虑。 来源/分类 B10-动态规划 [提交] [状态]转载于:https://www.cnblogs.com/Tidoblogs/p/11173398.html
