有 $n$ 根木棍，第 $i$ 根木棍的长度为 $L_i$，$n$ 根木棍依次连结了一起，总共有 $n-1$ 个连接处。

现在允许你最多砍断 $m$ 个连接处，砍完后 $n$ 根木棍被分成了很多段，要求满足总长度最大的一段长度最小。并且输出有多少种砍的方法使得总长度最大的一段长度最小，并将结果模 $10007$。

输入格式

第一行包含两个非负整数 $n, m$ ($1 \leq n \leq 50000, 0 \leq m \leq \min \{n-1, 1000\}$)。

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

输出格式

输出一行，包含两个整数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件。

题解

考虑第一问。来个二分答案吧，枚举长度的最大值，然后贪心求出至少要分几段，如果不够分，则令 $L \gets M + 1$，否则令 $R \gets M$，~~轻松水过~~。

考虑第二问。记第一问的答案为 $M$，由于计算方便，记前缀和 $S_i = \sum_{k=1}^i L_i$。

方案数这种玩意儿，看起来像个 DP，因此记 $f_{i, j}$ 表示前 $i$ 根木棍分成 $j$ 段 (即砍 $j-1$ 次) 的方案数，因此有初始状态 $f_{0, 0} = 1$ 和转移方程

答案为 $\sum\limits_{j=1}^{m+1} f_{n, j}$。于是时间复杂度为 $O(n^2 m)$，空间复杂度 $O(nm)$，都需要进一步优化。

首先空间这东西还是比较好优化的，由于 $f_{i, j}$ 只依赖于 $f_{k, j-1}$，故直接一个滚动数组把 $j$ 这一维滚掉即可，接下来考虑优化时间。

考虑条件 $S_i - S_k \leq M$，由于 $S_i$ 单调递增，所以当 $i$ 递增时，满足条件的 $k$ 的最小值式不减的 (否则原先的 $k$ 应该更小)，因此可以利用单调性确定 $k$，又由于它是一段连续区间的和，因此可以前缀和优化，即令 $g_i = \sum\limits_{k=i}^n f_{i, j}$，时间复杂度 $O(nm)$。

最后还有一个小技巧，由于 $k$ 的确定只和 $S_i$ 有关，不受 $f_{i, j}$ 的影响，因此可以预处理出对于每个 $i \in [1, n]$ 中，满足条件的 $k$ 的最小值，可以优化一波常数 ~~(听说从 $7 \texttt{s}$ 降到了 $3 \texttt{s}$？听说不优化洛谷过不去？)~~

代码

#include <bits/stdc++.h>
#define N 51221
using namespace std;

const int mod = 10007;

int n, k, t, i, j;
int L = 0, R = 0, M, ans;
int s[N], f[N], g[N], la[N]; // suffix sum

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

bool test(int x){
    int la = 0, cnt = 0, i;
    for(i = 1; i <= n; ++i)
        if(s[i] - s[la] > x)
            if(la = i - 1, ++cnt >= k) return false;
    return true;
}

int main(){
    scanf("%d%d", &n, &k); ++k; s[0] = 0;
    for(i = 1; i <= n; ++i){
        scanf("%d", &t); up(L, t);
        s[i] = s[i - 1] + t;
    }
    for(R = s[n]; L < R; )
        test(M = L + R >> 1) ? R = M : L = M + 1;
    for(t = 0, i = 1; i <= n; la[i] = t, ++i)
        for(; s[i] - s[t] > R; ++t);
    g[0] = 1;
    for(j = 1; j <= k; ++j){
        for(i = 1; i <= n; ++i)
            (f[i] = g[la[i]] - g[i]) < 0 ? f[i] += mod : 0;
        for(i = n; i >= 0; --i)
            add(g[i] = g[i + 1], f[i]);
        add(ans, f[n]);
    }
    printf("%d %d\n", R, ans);
    return 0;
}

坑

坑1：由于后面状态 ($i > 0$) 时 $f_{i, 0} = 0$，因此在滚动数组中没有必要置 $f_0 = 1$，可以令前缀和 $g_0 = 1$，然后再转移。

坑2：还有就是看题仔细，比如说砍断 $m$ 个连接处就是分成 $m+1$ 段，还有是最多砍断 $m$ 个。

题目描述

输入格式

输出格式

题解

代码

坑