思路
- 设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;
}