洛谷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;
}