题意

贝西要用干草包堆出一座塔 要求底下的干草堆的宽度一定大于等于上面的干草堆 然后干草堆是按顺序运来的 堆的时候也要求按顺序堆 运来的所有的草堆都要用到 不能将其中几个干草堆丢弃不用 贝西的目标是堆一坐最高的塔 要求输出最高的那个高度

这题贪心是不行的 但是也不能完全抛弃了贪心

题目要求我们从下到上递减 题目里也明确要求了 在铺第二层的时候 不能将干草包放到第一层

To be clear: she must not try to sneak a bale back on the foundation after a bale is placed on the second layer.

我们从下往上不好做 那我们可以从上往下做 那么我们只要下一层的大于等于这一层的

因为干草块要按顺序放 这个我们很容易就能想到用前缀和 如果我们用表示这一层的宽度 那么我们就要有 那么到这里就很明显了 可以直接去了 只要两个的差小于上一层 那么我们就可以转移 这个是的做法

我们可以发现 即然我们这一层一定小于下一层 那么同理往下也是这样 是单调的 那么我们就可以用一个单调队列去优化他

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
ll sum[N] , w[N] , dp[N] , cnt[N];
ll q[N];

void solve(){
    int n = read();
    for(int i = n ; i >= 1 ; --i)
        w[i] = read();
    for(int i = 1 ; i <= n ; ++i){
        sum[i] = sum[i - 1] + w[i];
    }
    int t = 0;
    q[++t] = 0;
    int h = 0;
    for(int i = 1 ; i <= n ; ++i){ 
        while(h < t && sum[q[h + 1]] + cnt[q[h + 1]] <= sum[i]) h++;
        cnt[i] = sum[i] - sum[q[h]];
        dp[i] = dp[q[h]] + 1;
        while(h <= t && sum[i] + cnt[i] <= sum[q[t]] + cnt[q[t]]) t--;
        q[++t] = i;
    }
    cout<<dp[n]<<endl;
}

int main(void){
    solve();

    return 0;
}