题目链接：BZOJ 1044
第一问是一个十分显然的二分，贪心Check()，很容易就能求出最小的最大长度 Len 。
第二问求方案总数，使用 DP 求解。
使用前缀和，令 Sum[i] 为前 i 根木棍的长度和。
令 f[i][j] 为前 i 根木棍中切 j 刀，并且满足最长长度不超过 j 的方案数，那么：
状态转移方程： f[i][j] = Σ f[k][j-1] ((1 <= k <= i-1) && (Sum[i] - Sum[k] <= Len))
这样的空间复杂度为 O(nm) ，时间复杂度为 O(n^2 m) 。显然都超出了限制。
下面我们考虑 DP 的优化。
1) 对于空间的优化。
这个比较显然，由于当前的 f[][j] 只与 f[][j-1] 有关，所以可以用滚动数组来实现。
f[i][Now] 代替了 f[i][j] ， f[i][Now^1] 代替了 f[i][j-1] 。为了方便，我们把 f[][Now^1] 叫做 f[][Last] 。
这样空间复杂度为 O(n) 。满足空间限制。
2) 对于时间的优化。
考虑优化状态转移的过程。
对于 f[i][Now] ，其实是 f[mink][Last]...f[i-1][Last] 这一段 f[k][Last] 的和，mink 是满足 Sum[i] - Sum[k] <= Len 的最小的 k ，那么，对于从 1 到 n 枚举的 i ，相对应的 mink 也一定是非递减的（因为 Sum[i] 是递增的）。我们记录下 f[1][Last]...f[i-1][Last] 的和 Sumf ，mink 初始设为 1，每次对于 i 将 mink 向后推移，推移的同时将被舍弃的 p 对应的 f[p][Last] 从 Sumf 中减去。那么 f[i][Now] 就是 Sumf 的值。
这样时间复杂度为 O(nm) 。满足时间限制。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; const int MaxN = 50000 + 5, Mod = 10007; int n, m, Len, MaxLen, Ans, Sumf;
int A[MaxN], Sum[MaxN], f[MaxN][2]; inline int gmax(int a, int b) {
return a > b ? a : b;
}
inline int gmin(int a, int b) {
return a < b ? a : b;
} bool Check(int x) {
if (x < MaxLen) return false;
int Add = 0, Cut = 0;
for (int i = 1; i <= n; i++) {
if (Add + A[i] > x) {
Cut++;
if (Cut > m) return false;
Add = 0;
}
Add += A[i];
}
return true;
} int main()
{
scanf("%d%d", &n, &m);
MaxLen = 0;
memset(Sum, 0, sizeof(Sum));
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
MaxLen = gmax(MaxLen, A[i]);
Sum[i] = Sum[i - 1] + A[i];
}
int l = 0, r = 50000000, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (Check(mid)) r = mid - 1;
else l = mid + 1;
}
Len = r + 1;
memset(f, 0, sizeof(f));
Ans = 0;
int Now = 0, Last = 1, Mink;
for (int i = 0; i <= m; i++) {
Sumf = 0;
Mink = 1;
for (int j = 1; j <= n; j++) {
if (i == 0) {
if (Sum[j] <= Len) f[j][Now] = 1;
else f[j][Now] = 0;
}
else {
while (Mink < j && Sum[j] - Sum[Mink] > Len) {
Sumf -= f[Mink][Last];
Sumf = (Sumf + Mod) % Mod;
++Mink;
}
f[j][Now] = Sumf;
}
Sumf += f[j][Last];
Sumf %= Mod;
}
Ans += f[n][Now];
Ans %= Mod;
Now ^= 1;
Last = Now ^ 1;
}
printf("%d %d\n", Len, Ans);
return 0;
}