题目大意：有$n(n\leqslant5\times10^4)$根木棍，连续放在一起，把它们分成$m(\leqslant10^3)$段，要求使得最长的段最短，问最短的长度以及方案数
题解：要使得最长的段最短，可以想到二分，然后方案数$DP$，令$f_{i,j}$表示现在是第$i$段，在第$j$根木棍后分段的方案数，$f_{i,j}=\sum\limits_{k=1\\dis(k,j)\leqslant res}^jf_{i-1,k}$（$dis(i,j)$表示第$i$根小木棍到第$j$根小木棍的总长度，$res$表示最短的长度），可以用双指针优化到$O(nm)$
卡点：
1. $check$程序返回了一个$bool$
2. 一个地方没取模
C++ Code：
#include <algorithm>
#include <cstdio>
#define maxn 500010
const int mod = 10007;
inline void reduce(int &x) { x += x >> 31 & mod; } int n, m, res, ans;
int li[maxn];
int f[2][maxn], now = 1, past = 0; inline int check(int mid) {
int cnt = 0, res = 0;
for (int i = 1; i <= n; ++i) {
if (cnt + li[i] > mid) {
cnt = 0;
++res;
}
cnt += li[i];
}
return res + static_cast<bool> (cnt);
} int main() {
scanf("%d%d", &n, &m); ++m;
{
int l = 1, r = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", li + i);
l = std::max(li[i], l);
r += li[i];
}
while (l <= r) {
int mid = l + r >> 1;
if (check(mid) <= m) r = mid - 1, res = mid;
else l = mid + 1;
}
}
printf("%d ", res);
f[now][0] = 1;
for (int i = 1; i <= m; ++i) {
static const int sz = sizeof f[now];
std::swap(now, past);
__builtin_memset(f[now], 0, sz);
int len = 0, up = f[past][0], lst = 0;
for (int j = 1; j <= n; ++j) {
len += li[j];
while (len > res) {
reduce(up -= f[past][lst]);
len -= li[++lst];
}
f[now][j] = up;
reduce(up += f[past][j] - mod);
}
reduce(ans += f[now][n] - mod);
}
printf("%d\n", ans);
return 0;
}