Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000
分析：我们要求最大矩形面积，那么我们应该求每个矩形向两边延伸的最大长度，最坏情况为0（n），必然TLE，那么我们可以应该DP的思想，用一个数组来保存一些结果。例如,dpl【i】表示从左边过来的最长，那么我们计算dpl【i】的时候，如果左边的比自己高，那么dpl【i】=dpl【i-1】，但是可能在前面还有更多符合情况的(比i-1低但是比i高），所以我们要用i-1-dp【i-1】
#include
#include
#include
#include
using namespace std;
#define ll __int64
ll dp[100010],l[100010],r[100010];
ll n;
int main()
{
while(~scanf("%I64d",&n)&&n)
{
int i;
for(i=1;
i<=n;
i++)
{scanf("%I64d",&dp[i]);
l[i]=r[i]=1;
}
ll t;
for(i=2;
i<=n;
i++)
{
t=i-1;
while(dp[t]>=dp[i]&&t>=1)
{
l[i]+=l[t];
t=t-l[t];
}
}
for(i=n-1;
i>=1;
i--)
{
t=i+1;
while(dp[t]>=dp[i]&&t<=n)
{
r[i]+=r[t];
t=t+r[t];
}
}
ll ans=0;
for(i=1;
i<=n;
i++)
{
t=dp[i]*(l[i]+r[i]-1);
if(ans 【HDU 1506 Largest Rectangle in a Histogram（最大连续矩阵面积）】
推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- LeetCode-28 实现strStr() KMP算法
- leetcode|递归、动态规划--Leetcode(python)