题解 P2511 【[HAOI2008]木棍分割】

· · 题解

首先最大的一段长度最小显然能马上想到二分， 先二分出这个长度，再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;
}

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