给你n个木棍连起来，可以切成m+1段，你要让最长的一段长度最小，求长度以及方案数量。n<=50000,m<=100

题解：第一个问二分一下就没了....

然后第二个问  用 f[i][j]表示前i个切成j段有多少种  f[i][j]=∑f[i-1][k]  s[k+1]+s[k+2]+...+s[i]<=ans1

很显然转移的部分是连续的一段，并且随着i增大而后移...所以可以用单调队列维护一下

复杂度nlogn+nm

#include
     
      #include
      
       #define mod 10007using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-') f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int f[2][50005];int s[50005];int n,m,ans1;bool check(int x){   // cout<<"check"<
       
        <
        
         x)return false;        nown+=s[i];if(nown>x){nown=s[i];num++;}    }    if(nown>0)num++;    return num<=m;}int main(){    n=read();m=read()+1;    for(int i=1;i<=n;i++)s[i]=read();    int l=1,r=1e9,mid;    while(l<=r)    {        mid=(l+r)>>1;        if(check(mid))ans1=mid,r=mid-1;        else l=mid+1;    }    f[0][0]=f[1][0]=1;    for(int i=1;i<=n;i++)s[i]+=s[i-1];    int pre=0,nown=1;    for(int j=1;j<=m;j++,pre=nown,nown^=1)    for(int i=1,tot=0,l=1,r=0;i<=n;i++)    {        tot=(tot+f[pre][r++])%mod;        while(l<=r&&s[r]-s[l-1]>ans1)tot=(tot+mod-f[pre][l-1])%mod,++l;        f[nown][i]=tot;       // cout<
         <<" "<
          
           <<" "<
           
            <<" "<
            
             <