常规DP超时：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N], s[N], f[N], g[N];
int q[N], l, r;
int main() {
int n;scanf("%d", &n);
for(int i = n; i; --i) scanf("%d", a+i);
s[0]=0;for(int i = 1; i <= n; ++i) s[i] = s[i-1] + a[i];
memset(f,0,sizeof(f));
memset(g,0x3f,sizeof(g));g[0]=0;
for(int i = 1; i <= n; ++i) {
for(int j=i-1;j>=0;--j)
if ( g[j] <= s[i]-s[j])
{
f[i] = f[j] + 1;
g[i] = s[i] - s[j];
break;
}
}
printf("%d\n", f[n]);
return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N], s[N], f[N], g[N];
int q[N], l, r;
int main() {
int n;scanf("%d", &n);
for(int i = n; i; --i) scanf("%d", a+i);
s[0]=0;for(int i = 1; i <= n; ++i) s[i] = s[i-1] + a[i];
memset(f,0,sizeof(f));
memset(g,0x3f,sizeof(g));g[0]=0;
l = 1; r = 1; q[1] = 0;
for(int i = 1; i <= n; ++i) {
while(l < r && s[q[l+1]]+g[q[l+1]] <= s[i]) ++l;
f[i] = f[q[l]] + 1;
g[i] = s[i] - s[q[l]];
while(l < r && s[q[r]]+g[q[r]] >= s[i]+g[i]) --r;
q[++r] = i;
}
printf("%d\n", f[n]);
return 0;
}