[bzoj1044]木棍分割

第一个问题可以用贪心+二分解决
第二个问题用f[i][j]表示i次分割后分割到j且满足条件的方案数，$f[i][j]=sum_{k<j且sum[j]-sum[k]<=ans}f[i-1][k]$
优化时间：前缀和优化，二分要先预处理出来（也可以用优先队列）
优化空间：发现f并没有什么用处，只需要记录前缀和数组，再对其滚动即可

#include<bits/stdc++.h>
using namespace std;
#define mod 10007
int n,m,ans,a[50005],b[50005],sum[2][50005];
bool pd(int k){
    int s=0,ans=0;
    for(int i=1;i<=n;i++){
        s+=a[i];
        if (s>k){
            ans++;
            s=a[i];
        }
    }
    return ans<=m;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int l=0,r=1000*n;
    for(int i=1;i<=n;i++)l=max(l,a[i]);
    while (l<r){
        int mid=(l+r>>1);
        if (pd(mid))r=mid;
        else l=mid+1;
    }
    for(int i=2;i<=n;i++)a[i]+=a[i-1];
    for(int i=1;i<=n;i++)sum[0][i]=(sum[0][i-1]+(a[i]<=l))%mod;
    for(int i=1;i<=n;i++)b[i]=lower_bound(a+1,a+n+1,a[i]-l)-a-1;
    ans=(a[n]<=l);
    for(int i=1;i<=m;i++){
        int p=(i&1);
        for(int j=i+1;j<=n;j++){
            r=(sum[p^1][j-1]-sum[p^1][b[j]]+mod)%mod;
            sum[p][j]=(sum[p][j-1]+r)%mod;
            if (j==n)ans=(ans+r)%mod;
        }
    }
    printf("%d %d",l,ans);
}