挺简单的题目，第一问二分明显。 第二问dp明显，有f[i][j]表示前i个切j刀，发现空间会炸，用单调队列dp那个样子做，每次更新一个左边界l，再用前缀和优化一下就好了。
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e5+5; const int INF=1e9; const int mo=1e4+7; int n,m; int a[N]; int f[N],sum[N],g[N]; bool pd(int x) { int sum=0,tim=0; fo(i,1,n) { if (a[i]>x)return 0; if (sum+a[i]<=x)sum+=a[i]; else sum=a[i],tim++; } if (tim>m)return 0; return 1; } int main() { scanf("%d%d",&n,&m); fo(i,1,n)scanf("%d",&a[i]); int l=1,r=INF,ans; while (l<=r) { int mid=(l+r)>>1; if (pd(mid))r=mid-1,ans=mid; else l=mid+1; } printf("%d ",ans); fo(i,1,n)sum[i]=sum[i-1]+a[i]; fo(i,1,n)if (sum[i]<=ans)f[i]=1; else break; int tot=f[n]; fo(i,1,m) { fo(j,1,n)g[j]=(g[j-1]+f[j])%mo; int l=1; memset(f,0,sizeof(f)); fo(j,i+1,n) { while (sum[j]-sum[l-1]>ans)l++; f[j]=(g[j-1]-g[l-2]+mo)%mo; } tot=(tot+f[n])%mo; } printf("%d\n",tot); }