【USACO】干草金字塔

题目描述

贝西要用干草包堆出一座金字塔。干草包会从传送带上陆续运来，依次出现 N 包，每包干草可 以看做是一个二维平面上的一个长方形，第 i 包干草的宽度是 W i ，长度统一为 1。 金字塔的修建有几个规定，首先，为了建筑稳定，塔一定要形成类似“金”字的样子，即塔的上 层宽度不能超过下层宽度，而且每层的干草包必须紧靠在一起，不能出现缝隙。其次，由于干草是陆 续送来的，所以先送来的干草放在较低层。贝西会选择最先送来的几包干草，堆在地上作为第一层， 然后再把紧接着送来的几包干草包放在第二层，再铺建第三层……重复这个过程，一直到所有的干草 全部用完。最后，贝西不喜欢浪费，所有干草包一定要用上，不能弃置不用。贝西的目标是建一座最 高的金字塔，在遵循上述规定的前提下，她可以任意决定在金字塔的每一层布置多少连续的干草包。 请你来帮助她完成这个任务吧。

输入

• 第一行：单个整数 N，1 ≤ N ≤ 100000 • 第二行到第 N + 1 行：第 i + 1 行有一个整数 W i ，1 ≤ W i ≤ 10000

输出

• 单个整数：表示可以建成的最高高度

样例输入

3 1 2 3

样例输出

2

提示

将 1 和 2 放在第一层，将 3 放在第二层

 

题解：

我们从上往下搭 方便转移

设F[i]为后i个最多搭多少层，p[i]为最下面一层为多少

很容易得出 如果满足sum[i]-sum[j]>=p[j] 就可以转移F[i]=F[j]+1

移项sum[i]>=sum[j]+p[j] 所以我们要选出满足条件的最大sum[j]+p[j] 这样转移来的答案一定是最优的

于是开单调队列维护sum[j]+p[j]

 

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100015; 7 int gi(){ 8 int str=0;char ch=getchar(); 9 while(ch>'9' || ch<'0')ch=getchar(); 10 while(ch>='0' && ch<='9')str=str*10+ch-48,ch=getchar(); 11 return str; 12 } 13 int a[N],sum[N],f[N],p[N],q[N]; 14 int main() 15 { 16 int n=gi(); 17 for(int i=1;i<=n;i++)a[i]=gi(); 18 for(int i=n;i>=1;i--)sum[i]=sum[i+1]+a[i]; 19 int ans=0,l=1,r=1; 20 for(int i=n;i>=1;i--) 21 { 22 while(l<r && sum[i]>=sum[q[l+1]]+p[q[l+1]])l++; 23 f[i]=f[q[l]]+1; 24 p[i]=sum[i]-sum[q[l]]; 25 if(f[i]>ans)ans=f[i]; 26 while(l<=r && sum[i]+p[i]<=sum[q[r]]+p[q[r]])r--; 27 q[++r]=i; 28 } 29 printf("%d",ans); 30 return 0; 31 }

 

 

 

转载于:https://www.cnblogs.com/Yuzao/p/7000964.html