中文题意

第一行输入代表下面会有个草方块，并且给出的是草方块的宽度，给出的草方块高度都是。现在要你不重不漏的从编号小到编号大堆积草方块，你可以把草方块放在新的一层时，首先要满足它堆上上一层之后，宽度小于等于下一层。问这样的前提中你可以堆积的最高的草方块高度是多少？

Solution

对于这样的问题，贪心应该是没跑了。但是我们首先想一个贪心的策略，我们不能丢弃草方块，那么我们就从后往前处理这些草堆。我们就简单的贪心让最高层尽可能小，看看这样行不行，多枚举几组，我们就可以找到这样一组数据把你掉，就是我们上方贪心过程中导致我们底层一定要选很厚的一些。例如：

7
11 8 2 1 2 6 5

按照上方的，我们要让最高处最短那就倒序来看
5 \ 6 \ 2 1 2 8 11
我们只能得到3组
但是很明显，如果我们稍微考虑的话。可以得到这样的序列。
5 \ 6 2 \ 1 2 8 \ 11
我们可以得到正确的答案4

通过上方的测试很明显发现我们最开始的贪心是错误的，但是我们好像发现了另外一种贪心策略，那就是让底层结尾的时候尽可能窄一点。我们可以把这些草方块类比成一些面积，我们要运用全部的草方块，也就是相当于给我们图形面积一定，但是要你求解最高的高，也就是我们要让底尽可能小。那么我们让最底层在尽可能小的情况下，它的上一层尽可能和它一样大。

那么如何具体求解？我们考虑动态规划。

同样的我们还是需要把数组进行翻转，翻转之后，我们可以求解一次前缀和，得到。

我们使用代表第层放在最顶上的时候，第层所在的层数宽度。

我们使用代表第层放在最顶上的时候，它的最高高度是多少？

那么我们写出状态转移方程：，实现这个转移的前提，那就是，并且我们希望每次转移上面都要尽可能多拿一点这样下面就可以少一点，就会使得最下面一层最小。

这里我们发现每次做转移时间是，枚举又是，总的时间复杂度就是。

我们看到这个转移方程，做个化简最大的，使用单调队列进行优化。

对于不符合的队列头部直接，对于每次队列的尾部，思考之前一个转移点，如果以及，是不是说明进来了，就一定没有机会了，直接。做好这样的优化之后总的时间复杂度就是了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
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; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e5 + 7;
int n, m;
int p[N], sum[N], width[N], f[N];
deque<int> q;
int pos;

int calc(int x) {
    return sum[x] + width[x];
}

void solve() {
    n = read();
    repp(i, n, 1)    p[i] = read();
    rep(i, 1, n)    sum[i] = sum[i - 1] + p[i];
    int ans = 0;
    rep(i, 1, n) {
        while (q.size() and sum[i] >= calc(q.front()))
            pos = q.front(), q.pop_front();
        f[i] = f[pos] + 1;
        width[i] = sum[i] - sum[pos];
        while (q.size() and calc(i) <= calc(q.back()))
            q.pop_back();
        q.push_back(i);
    }
    print(f[n]);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}