题意很简单，给出 n 个数字，要分成最多的区间数，使每个区间内的和大于等于前一个区间和。
思路：sum[]表示前缀和，dp[i]表示前 i 个数字的最多区间数，presum[i]表示只考虑前 i 个数时，最后一个区间的和，这样只要从末端枚举直到和大于等于 presum[j]就 break。
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
long long sum[3010];
long long presum[3010];
int dp[3010];
int main(){
int n;
sum[0] = 0;
while(~scanf("%d", &n)){
presum[0] = 0;
dp[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%lld", &sum[i]);
sum[i] += sum[i-1];
}
for(int i = 1; i <= n; i++){
for(int j = i-1; j >= 0; j--){
long long temp = sum[i]-sum[j];
if(temp >= presum[j]){
presum[i] = temp;
dp[i] = dp[j]+1;
break;
}
}
}
cout << dp[n] << endl;
}
return 0;
}