Tower of Hay

思路

• 设cnt[i]表示当前层摆放的宽度，h[i]表示当前层摆放的最大高度
• 因为上层的宽度不能超过下层的宽度，所以我们可以从后往前优先考虑上层宽度
• 利用前缀和的思想来求放在同一层合并后的宽度

代码

// Problem: Tower of Hay
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/24881
// Memory Limit: 65536 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n;
int w[N],s[N],cnt[N],h[N];

void solve(){
    cin>>n;
    per(i,n,1) cin>>w[i];
    rep(i,1,n) s[i]=s[i-1]+w[i];
    rep(i,1,n){
        per(j,i-1,0){
            if(s[i]-s[j]>=cnt[j]){
                h[i]=max(h[i],h[j]+1);
                cnt[i]=s[i]-s[j];
                break;
            }
        }
    }
    cout<<h[n]<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}