[BZOJ 1044] [HAOI2008] 木棍分割 【二分 + DP】

题目链接: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;
}

  

上一篇:Happy 2006 POJ - 2773 容斥原理+二分


下一篇:hdu-4678-sg