彩票网站的推荐怎么做,中国十大知名网站建设,网站子页怎么做,阜阳恒亮做网站多少钱正题
POJ题目链接:http://poj.org/problem?id2559 luogu评测记录:https://www.luogu.org/recordnew/lists?uid52918pidSP1805 大意
有n个高度不同#xff0c;宽度为1的长方形排列在一起。找到一个长方形使其面积最大 解题思路
我们先考虑单调递增的情况 …正题
POJ题目链接:http://poj.org/problem?id2559 luogu评测记录:https://www.luogu.org/recordnew/lists?uid52918pidSP1805 大意
有n个高度不同宽度为1的长方形排列在一起。找到一个长方形使其面积最大 解题思路
我们先考虑单调递增的情况 这样的话就只有以上几种情况。 然后我们考虑不是递增的情况那么上面的就没有用了 我们就可以将其去掉 我们考虑用单调栈如果单调上升就加入栈顶不然就将栈弹出直到加入新元素之后是单调的在途中统计弹出的宽度和然后计算之后再将宽度合并到新的元素中。 code
#includecstdio
#includestack
#includealgorithm
using namespace std;
stackint a;
int n,wide,h[100010],w[100010];
long long maxs;
int main()
{while(1){scanf(%d,n);if (!n) break;while(!a.empty()) a.pop();maxs0;wide0;h[n1]0;for(int i1;in1;i){if(i!n1)scanf(%d,h[i]);if(a.empty()||h[a.top()]h[i])//单调递增的{a.push(i);w[i]1;}else{wide0;while (!a.empty()h[a.top()]h[i])//维护单调性{widew[a.top()];//累计宽度maxsmax(maxs,(long long)wide*h[a.top()]);//计算答案a.pop();//出栈}a.push(i);w[i]wide1;//合并宽度}}printf(%lld\n,maxs);}
}
