题解：P2511 [HAOI2008] 木棍分割

· · 题解

题目描述

给 n 个木棍，最多分成 m+1 段，输出连续长度和的最大值的最小值，并计算出方案数。

Q1：二分+贪心

考虑枚举的长度中包含尽可能多的木棍，如果枚举的长度符合要求，那么将右边界修改为枚举的长度 mid;否则将左边界修改为 mid+1。

主要代码如下：

while(r>l)
    {
        int mid=(r+l)>>1,sum=0,tot=0;
        for(int i=1;i<=n;i++)
        {
            sum+=a[i];
            if(sum==mid){++tot,sum=0;continue;}
            if(sum+a[i+1]>mid) ++tot,sum=0;
        }
        if(sum) ++tot;
        if(tot>m+1) l=mid+1;
        else r=mid;
    }

Q2：前缀和优化DP+滚动数组

用 b 数组记录前缀和，用 f[i][j] 表示将前 i 段木棍切 j 次的最大方案数（切 j 次是分成了 j+1 段），在区间和小于 l 的情况下枚举 k,于是得到转移方程：

f[i][j] = \sum \limits_{k=0}^{i-1} f[k][j]$,$k$ 满足 $b[i]-b[k]≤l

显然，上面 O(mn^2) 的复杂度是不能接受的，盯着我们的DP转移方程我们发现，由于区间和的线性，我们的 k 有一个最小值，使后面的 k 都成立，所以可以对其进行预处理，代码如下：

for(int i=1;i<=n;i++)
        while(j<n&&b[j+1]-b[i]<=l) pre[++j]=i;

打到现在，我们发现了一个问题,f[50000][1000] 无法实现。于是再次回到 DP 方程，经过一个半小时的瞪眼后，我们又发现 f[i] 只受 f[i-1] 的影响，所以很自然的想到使用滚动数组，于是我们得到了以下代码：

    for(int i=1;i<=n;i++)
        g[i]=g[i-1]+(b[i]<=l);
    for(int j=1;j<=m;j++)
    {
        for(int i=2;i<=n;i++) f[i]=g[i-1]-g[pre[i]-1];
        for(int i=1;i<=n;i++) g[i]=(g[i-1]+f[i])%mod;
        ans=(ans+f[n])%mod;
    }

正当我们兴高采烈地等着 AC 时，去发现 WA 了两个点，于是又开始瞪眼，最后瞪了半个小时（其实是旁边的神犇看出来的），我们的 f[i] 是做的减法，如果前者取模后小于后者，则会出现负数，所以应该输出(ans%mod+mod)%mod,最后愉快 AC (〃'▽'〃)

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+5,mod=1e4+7;
int a[N],b[N],f[N],g[N],pre[N];
int read()
{
    int x=0,a=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') a=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
    return x*a;
}
void write(int x)
{
    if(x<0)x*=-1,putchar('-');
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}
signed main()
{
    int n,m,r,l=0,j=0,ans=0;
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[i]=b[i-1]+a[i];
        l=max(l,a[i]);
    }
    r=b[n];
    while(r>l)
    {
        int mid=(r+l)>>1,sum=0,tot=0;
        for(int i=1;i<=n;i++)
        {
            sum+=a[i];
            if(sum==mid){++tot,sum=0;continue;}
            if(sum+a[i+1]>mid) ++tot,sum=0;
        }
        if(sum) ++tot;
        if(tot>m+1) l=mid+1;
        else r=mid;
    }
    for(int i=1;i<=n;i++)
        g[i]=g[i-1]+(b[i]<=l);
    for(int i=1;i<=n;i++)
        while(j<n&&b[j+1]-b[i]<=l) pre[++j]=i;
    for(int j=1;j<=m;j++)
    {
        for(int i=2;i<=n;i++) f[i]=g[i-1]-g[pre[i]-1];
        for(int i=1;i<=n;i++) g[i]=(g[i-1]+f[i])%mod;
        ans=(ans+f[n])%mod;
    }
    write(l),putchar(' '),write((ans%mod+mod)%mod);
    return 0;
}