自动搬运

查看原文

来自洛谷，原作者为

	niiick **

搬运于2025-08-24 21:38:29，当前版本为作者最后更新于2018-10-30 12:03:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先最大的一段长度最小显然能马上想到二分， 先二分出这个长度，再DP求解方案数

假设求解出的长度为$x$， 设$dp[i][j]$表示前$j$个木棍，分成$i$组的方案数(注意是分$i$组，不是切$i$下)

先初始化$dp[1][i]=[sum[i]<=x]$

$dp[i][j]=\sum_{l=k}^{j-1}dp[i-1][l]$其中$k$为满足$sum[j]-sum[k]<=x$的最小的$k$

$ans=\sum_{i=1}^{m+1}dp[i][n]$

这样的方程复杂度$O(n^3)$，实测一个点都过不了

我们发现每次找到第一个$sum[j]-sum[k]<=x$的$k$后，由于$sum$单调性，对于后面的一定也满足条件。 所以可以用前缀和维护$dp$数组，即$sum[i][j]=\sum_{k=0}^jdp[i][k]$

那么方程变为$dp[i][j]=sum[i-1][j]-sum[i-1][k-1]$

但是到这里我们还是发现狂T不止，原因出在我们对于相同的$j$重复去找$k$，这显然不必要

我们一开始先预处理对于每个$j\in[1,n]$，满足$sum[j]-sum[k]<=x$的第一个$k$是什么

int k=0;
for(int i=1;i<=n;++i)
for(;k<i;++k)
if(sum[i]-sum[k]<=x){ rem[i]=k; break;}

再次注意这里由于sum的单调性，$k$不用每次置0，否则你还是狂T不止

到这里就结束了吗，还没！

我们发现每次转移$dp[i][]$的时候都只用到$sum[i-1][]$， 显然造成了不必要的空间浪费， 可以直接滚掉$dp$和$sum$的第一维

//niiick
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;

int read()
{
    int x=0,f=1;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}

const int mod=10007;
const int maxn=50010;
int n,m,mx,ans;
int a[maxn],sum[maxn];
int dp[maxn],S[maxn];
int rem[maxn];

int check(int x)
{
    int tot=0,len=0;
    for(int i=1;i<=n;++i)
    {
        if(len+a[i]>x) tot++,len=a[i];
        else len+=a[i];
        if(tot>m) return 0;
    }
    return tot<=m;
}

int DP(int x)
{
    int k=0;
    for(int i=1;i<=n;++i)
    for(;k<i;++k)
    if(sum[i]-sum[k]<=x){ rem[i]=k; break;}
    
    int res=(sum[n]<=x);
    for(int i=1;i<=n;++i)
    {
    	if(sum[i]<=x) dp[i]=1;
    	S[i]=(S[i-1]+dp[i])%mod;
    }
    
    for(int i=2;i<=m+1;++i)
    {
        for(int j=1;j<=n;++j)
        {
            dp[j]=S[j-1];
            if(rem[j]-1>=0) dp[j]=((dp[j]-S[rem[j]-1])%mod+mod)%mod;//注意减法出现负数
        }
        for(int j=1;j<=n;++j)
        S[j]=(S[j-1]+dp[j])%mod;
        
        res=(res+dp[n])%mod;
    }
    return res;
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i) 
    a[i]=read(),sum[i]=sum[i-1]+a[i],mx=max(mx,a[i]);
    
    int L=mx,R=sum[n],mid;
    while(L<R)
    {
        mid=L+R>>1;
        if(check(mid)) ans=mid,R=mid;
        else L=mid+1;
    }
    printf("%d %d",ans,DP(ans));
    return 0;
}

最后还是想再吐槽一下这题数据范围完全不科学啊

$O(nm)$的DP+$O(nlog(n*L_i))$的二分，大概出题人感性觉得能过就这样了吧