肯定是二分+dp
但只能想出n^2m dp
感觉每个数字的状态都和前面的数字和有关，但划分是灵活的，可以衍生出多种前缀和的情况。
看了题解，但是：
、、 、一脸懵逼，，代码是还pascal的、、
自己推（meng）理（bi）了一个上午，终于推出来了：
第一问是二分裸题、
第二问是前缀和优化dp
在对n^2m dp的疯狂优化之后，终于写出了两组递推式：
f[r]=((qqsum[r-1]-qqsum[l-2])%M+M)%M; qsum[r]=(qsum[r-1]+f[r])%M;
原理：根据传统区间dp思想，枚举区间的右端点，但由于随着右端点的不断增大，左端点一定是单调向右移的
在（左端点 ~ 右端点-1 ）这个区间内都是在<=ans内合法的，左端点往左的就是分出的j-1次的方案数；；
我们只需求出 左端点 ~ 右端点-1 的点往左的上一个划分的方案数之和
所以就要用前缀和： 右端点的方案数=左端点-1的方案数+左端点的方案数+左端点+1的方案数+左端点+2的方案数+...+右端点-2的方案数+右端点-1的方案数；
=右端点-1的方案数前缀和-左端点-2的前缀和
大概的流程：
像不像一只爬虫在树枝上爬？
没做过这种算法（其实就没见过）的题，所以我们是可以利用题目的性质、特点（单调性、逻辑）自己写出算法的（甚至有可能创出新的算法）
算法竞赛的本质就是考验你的分析能力，并用程序描述你的分析结果
#include<iostream> #include<cstdio> using namespace std; #define N 50005 #define M 10007 int mid,jishu,a[N],ya,n,m,i,ans1,sum[N],daan,qian[N],qqsum[N],f[N],qsum[N],j,l,r; bool zai; int erfen(int l,int r) { while(l<r) { mid=(l+r)>>1; ya=0; jishu=0; zai=0; for(int i=1;i<=n;i++) { ya+=a[i]; if(ya>mid) {ya=a[i],jishu++; if(ya>mid||jishu>m)zai=1; } } if(zai){l=mid+1;continue;} else r=mid; } return l; } int main() { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); ans1=erfen(1,50000000); // cout<<ans1; sum[0]=1; for(i=1;i<=n;i++) { qian[i]=a[i]+qian[i-1]; } //预处理1的 ya=0; for(i=1;i<=n;i++) { ya+=a[i]; if(ya<=ans1)f[i]=1; qqsum[i]=(f[i]+qqsum[i-1])%M; } daan+=f[n]; for(j=2;j<=m+1;j++) { l=j;r=j; for(r=j;r<=n;r++) { while(qian[r]-qian[l-1]>ans1)++l; f[r]=((qqsum[r-1]-qqsum[l-2])%M+M)%M; qsum[r]=(qsum[r-1]+f[r])%M; } daan+=f[n]; daan%=M; for(i=1;i<=n;i++) { qqsum[i]=qsum[i]; } } printf("%d %d",ans1,daan%M); }时间很慢（没有任何优化，时间应该是 n*3*m的、、）
但bzoj能过，洛谷上过不了，因为时限错了 %%lych ORZ ORZ
