洛谷P2511 [HAOI2008]木棍分割题解

题目链接：P2511 [HAOI2008]木棍分割

题意：

有 \(n\) 根木棍, 第 \(i\) 根木棍的长度为 \(L_i\) ， \(n\) 根木棍依次连结了一起，总共有 \(n-1\) 个连接处。现在允许你最多砍断 \(m\) 个连接处，砍完后 \(n\) 根木棍被分成了很多段，要求满足总长度最大的一段长度最小，并且输出有多少种砍的方法使得总长度最大的一段长度最小，并将结果 \(\bmod 10007\) 。

输入格式：

第一行有 \(2\) 个数 \(n,m\) 。

接下来 \(n\) 行每行一个正整数 \(L_i\) ，表示第 \(i\) 根木棍的长度。

输出格式：

输出有 \(2\) 个数，第一个数是总长度最大的一段的长度最小值，第二个数是有多少种砍的方法使得满足条件。

数据范围：

\(1 \le n\le 5\times 10^4,~ 0\le m\le \min\{n-1,1000\},~1\le L_i\le 1000\)

第一问比较简单，考虑二分然后贪心地去切就好了

考虑第二问怎么做。~~一眼计数型线性dp~~。

不妨假设第一问求出的答案为 \(M\) 。

设 \(f_{i,j}\) 表示前 \(i\) 个木棍分成 \(j\) 段的方案数，则 \[ f_{0,0} = 1 \\\\ f_{i,j} = \sum\limits_{1 \le k < i\land S_i-S_k \le M} f_{k,j-1} \] 其中 \(S_i\) 是前缀和，即 \(S_i = \sum_{j=1}^{i} L_j\) 。

则最终答案为 \(\sum_{i=1}^{m+1} f_{n,i}\) 。

目前为止的时空复杂度都巨大，无法通过此题，考虑优化。

首先 \(j\) 的答案可以从 \(j-1\) 推出，于是我们把这一维滚掉。

显然这里的 \(k\) 随着 \(i\) 的递增单调不降

然后前缀和优化一下，即令 \(g_i = \sum_{t=i}^{n}f_{t,j}\)

这样就可以用 \(g_i-g_{k-1}\) 求得这一段的和了。

注意到 \(k\) 仅与 \(S_i\) 有关，与 \(f_{i,j}\) 无关，

考虑预处理一下每个 \(i \in [1,n]\) ，满足的 \(k\) 的最小值，可以优化常数。

时间复杂度 \(O(nm)\) ，空间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(5e4+15))
const int mod=1e4+7;

void up(int &x,int y){ x < y ? x = y : 0;}
void add(int &x,int y){ (x+=y) >= mod ? x-=mod : 0;}

int n,k,mx,l,r,res;
int sum[N],pre[N],f[N],g[N];
bool work(int mid)
{
    int lst=0,cnt=0;
    for(int i=1; i<=n; i++)
        if(sum[i] - sum[lst] > mid)
            if(lst=i-1, ++cnt >= k) return 0;
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; ++k;
    for(int i=1,x; i<=n; i++)
    {
        cin >> x; up(mx,x);
        sum[i] = sum[i-1] + x;
    }
    int l=mx,r=sum[n];
    while(l < r)
    {
        int mid = (l+r) >> 1;
        work(mid) ? r=mid : l=mid+1;
    }
    for(int i=1,j=0; i<=n; pre[i]=j, i++)
        for(; sum[i]-sum[j] > l; ++j);
    g[0]=1;
    for(int j=1; j<=k; j++)
    {
        for(int i=1; i<=n; i++)
            ((f[i] = g[pre[i]] - g[i]) < 0) ? f[i] += mod : 0;
            // f[i]=g[pre[i]]-g[i];

        for(int i=n; i>=0; i--)
            add(g[i]=g[i+1], f[i]); // g[i]=g[i+1]+f[i];
        add(res, f[n]);
    }
    cout << l << ' ' << res << '\n';
    return 0;
}