hdu1506 dp：长度不等的山峰找最大面积矩形（或者用单调栈）-白红宇

hdu1506 dp：长度不等的山峰找最大面积矩形（或者用单调栈）

阅读量：5962 次

发布时间：2019-06-19

本文共 1679 字，大约阅读时间需要 5 分钟。

先用单调上升栈处理左右端点A了，稳稳地O(n)做法

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 stack
          
           s,s1; 7 int l[100005],r[100005],a[100005]; 8 int main() 9 {10     int i,n,y;11     while (~scanf("%d",&n)&&n)12     {13         while (!s.empty()) {s.pop(); s1.pop();}14         for (i=1;i<=n;i++)15         {16             scanf("%d",&a[i]);17             while (!s.empty())18             {19                 y=s.top();20                 if (y
           
            =1;i--)29 {30 while (!s.empty())31 {32 y=s.top();33 if (y
            
             x) x=(long long)a[i]*(long long)(r[i]-l[i]+1);43 printf("%I64d\n",x);44 }45 return 0;46 }

View Code

妈蛋竟然没有dp找左右端点快，暗想一定是数据有点弱

1 #include
      
        2 #include
       
         3 int a[100005],l[100005],r[100005]; 4 int main() 5 { 6     int i,n,y; 7     while (~scanf("%d",&n)&&n) 8     { 9         for (i=1;i<=n;i++) scanf("%d",&a[i]);10         l[1]=1;11         for (i=2;i<=n;i++)12         {13             y=i;14             while (y>1&&a[i]<=a[y-1]) y=l[y-1];15             l[i]=y;16         }17         r[n]=n;18         for (i=n-1;i>=1;i--)19         {20             y=i;21             while (y
        
         <=a[y+1]) y=r[y+1];22             r[i]=y;23         }24         long long  x=0;25         for (i=1;i<=n;i++)26             if ((long long)a[i]*(long long)(r[i]-l[i]+1)>x) x=(long long)a[i]*(long long)(r[i]-l[i]+1);27         printf("%I64d\n",x);28     }29 }

View Code

注意dp的状态转移，是比较当前最左的左边一个和自己的大小

传送门：

转载于:https://www.cnblogs.com/xiao-xin/articles/4065836.html

你可能感兴趣的文章

在MySQL中，不要使用“utf8”。使用“utf8mb4”

查看>>

了解 IT 认证价值

查看>>

关于安卓的ViewStub，我有几句话想说。。。

查看>>

Android AOSP基础（一）趁周末用VirtualBox 安装 Ubuntu吧