首页 > 代码库 > 干草金字塔

干草金字塔

干草金字塔

时间限制: 1 Sec  内存限制: 128 MB

题目描述

贝西要用干草包堆出一座金字塔。干草包会从传送带上陆续运来,依次出现 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个干草能够达到的最大高度。

于是很容易想到暴力,每次j向后枚举就可以了,但是n≤100000,O(n^2)肯定会超时,所以考虑优化。

定义sum[i]为前缀和,g[i]表示后i个堆到f[i]高度时(实际上就是达到最大高度时)最后一层的最小宽度。

sum[i]和f[i]都是递增的,g[i]相对于上一个状态也是递增的。因此我们只需要找到使g[i]变化量最小的值就可以了。

为什么是最小值?很显然,把后i个干草堆想象成一个面积为sum[i]的金字塔,那么要使f[i]尽可能的大,g[i]就要尽可能的小。

接下来是怎么找,很显然g[i]相对与g[j]的变化量为s=sum[i]-sum[j]-g[j]=sum[i]-(sum[j]+g[j]),要使s最大,sum[j]+g[j]要最小,显然sum[j]+g[j]与i没有关系,所以考虑使用优先队列保存sum[j]+g[j]的值,每次取小于sum[i]的最大值就可以了。

因为sum[i]是递增的,所以当存在另一个比sum[i]小的更大的值时,前面的就可以出队了。

AC代码如下:

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
using namespace std;
int n,f[100001],a[100001],sum[100001],g[100001],s[100001];
int q[100001],head,tail;
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=n;i>=1;i--)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+a[i];
    }
    q[tail++]=0;
    for(i=1;i<=n;i++)
    {
        while(head+1<tail&&s[q[head+1]]<=sum[i])head++;
        f[i]=f[q[head]]+1;
        g[i]=g[q[head]]+sum[i]-s[q[head]];
        s[i]=sum[i]+g[i];
        while(tail>head&&s[q[tail-1]]>s[i])tail--;
        q[tail++]=i;
    }
    cout<<f[n];
    return 0;
}

 

 

 

干草金字塔