题意

给出一个长度为$n$数列，将其分为最多$m+1$段，使得和最大的一段的和最小，求这个长度与方案数

数据范围：$n \le 50000,0 \le m \le \min(n-1,1000)$

题解

对于第一个问题，二分答案求解，记答案为$ans$
对于第二个问题，$dp$求解
用$f[i][j]$表示前$i$个数划分为$j$段的方案数
记$s[i]$为前缀和，首先有$$f[i][1]=[s[i] \le ans]$$
另有$$dp[i][j]=\sum_{k=lst[i]}^{i-1}dp[k][j-1]$$
其中$lst[i]$表示满足$s[i]-s[j] \le ans$的最小$j$，即上一个分段的地方，在区间中枚举上一个分段的地方，计入答案
最终答案为$$\sum_{i=0}^{m+1}dp[n][i]$$
但是这样$dp$的复杂度为$O(N^3)$，需要进行优化
发现求和部分被重用多次，考虑前缀和优化
并且发现$j$一定从$j-1$转移而来，可以去掉第二维

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50000+10;
const int M=1000+10;
const int mod=10007;
int n,m,l,r,ans,tot;
int a[N],s[N],lst[N],dp[N],sdp[N];
inline bool check(int x){
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(sum+a[i]>x){
            sum=a[i];
            cnt++;
        }
        else sum+=a[i];
        if(cnt>m)
            return 0;
    }
    return cnt<=m;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        l=max(l,a[i]);
        s[i]=s[i-1]+a[i];
    }
    for(r=s[n];l<=r;){
        int mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d",ans);
    for(int i=1,k=0;i<=n;i++){
        for(;k<i && s[i]-s[k]>ans;k++);
        lst[i]=k;
    }
    tot=s[n]<=ans;
    for(int i=1;i<=n;i++){
        dp[i]=s[i]<=ans;
        sdp[i]=(dp[i]+sdp[i-1])%mod;
    }
    for(int i=2;i<=m+1;i++){
        for(int j=1;j<=n;j++)
            dp[j]=((sdp[j-1]-sdp[lst[j]-1])%mod+mod)%mod;
        for(int j=1;j<=n;j++)
            sdp[j]=(dp[j]+sdp[j-1])%mod;
        (tot+=dp[n])%=mod;
    }
    printf(" %d",tot);
    return 0;
}