看到这题，自然的想到 DP 啦！
如果设 $f_{i,j}$ 为到第 $i$ 个位置前面的都合法且最后一段和为 $j$ 是否可行，那么转移十分显然，但是状态会炸。
此时我们考虑在状态上进行优化来减少时间，把 $f_i$ 设为到第 $i$ 个位置分段数量最多的情况下且最后一段和最少的和，以及能分成几段就好了。
不难写出 $n^2$ 的代码：
#include<iostream> using namespace std; int n; int a[200005],s[200005]; int f[200005][2];//满足分段尽可能多的情况下，最后一段和的最小值 int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=s[i-1]+a[i]; } for(int i=1;i<=n;i++){ f[i][0]=1; f[i][1]=s[i]; } for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ if(s[i]-s[j]>=f[j][1]&&f[j][0]+1>=f[i][0]){ if(f[j][0]+1==f[i][0])f[i][1]=min(f[i][1],s[i]-s[j]); else{ f[i][0]=f[j][0]+1; f[i][1]=s[i]-s[j]; } } } } cout<<f[n][0]; return 0; }
接着，我们根据那一行 if 的不等式，进行变换得到 ${s_i}>={s_j}+f_{j,1}$，所以思路显然。
算完 $f_i$ 后，把 $i$ 加到 $s_i+f_{i,1}$ 上，查询就查询 $<=s_i$ 位置上最大的 $f_{x,0}$，如果有多个相同的，那么取 $x$ 最大的，这样一来最后一段的和才能最小。
代码如下：（tjq 说可以单调队列，但对热爱线段树的我来说这样就够了吧。）
#include<iostream> using namespace std; const int inf=2000200000; int n,rt,cnt; int a[200005],s[200005]; int f[200005][2];//满足分段尽可能多的情况下，最后一段和的最小值 int mx[7000005],ls[7000005],rs[7000005];//单点修改，区间查询 bool cmp(int i,int j){//i 是否比 j 好 if(i==0)return false; if(j==0)return true; if(f[i][0]<f[j][0])return false; else if(f[i][0]==f[j][0]){ if(i<j)return false; return true; } return true; } void update(int l,int r,int &k,int x,int y){ if(!k)k=++cnt; if(l==r){ if(!cmp(mx[k],y))mx[k]=y; return; } int mid=l+r>>1; if(x<=mid)update(l,mid,ls[k],x,y); else update(mid+1,r,rs[k],x,y); if(cmp(mx[ls[k]],mx[rs[k]]))mx[k]=mx[ls[k]]; else mx[k]=mx[rs[k]]; } int query(int l,int r,int k,int x,int y){ if(x<=l&&y>=r)return mx[k]; int mid=l+r>>1,res=0; if(x<=mid)res=query(l,mid,ls[k],x,y); if(y>mid){ int tmp=query(mid+1,r,rs[k],x,y); if(cmp(tmp,res))res=tmp; } return res; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=s[i-1]+a[i]; } for(int i=1;i<=n;i++){ int j=query(1,inf,1,1,s[i]); f[i][0]=f[j][0]+1; f[i][1]=s[i]-s[j]; // for(int j=1;j<i;j++){ // if(s[i]-s[j]>=f[j][1]&&f[j][0]+1>=f[i][0]){ // if(f[j][0]+1==f[i][0])f[i][1]=min(f[i][1],s[i]-s[j]); // else{ // f[i][0]=f[j][0]+1; // f[i][1]=s[i]-s[j]; // }//s[i]>=s[j]+f[j][1] // //算完一个后，将 f[j][0] 的 s[j]+f[j][1] 加到 xds 中，查询 <= s[i] 位置上的最大值 // } // } update(1,inf,rt,s[i]+f[i][1],i); } cout<<f[n][0]; return 0; }