「BZOJ1044」[HAOI2008]木棍分割

Description

nn根木棍, 第ii根木棍的长度为Li,nL_i,n根木棍依次连结了一起, 总共有n1n-1个连接处. 现在允许你最多砍断mm个连
接处, 砍完后nn根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长
度最大的一段长度最小. 并将结果(mod10007)\pmod{10007}

Input

输入文件第一行有22个数n,mn,m.接下来nn行每行一个正整数LiL_i,表示第ii根木棍的长度

Output

输出有22个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.

Sample Input

1
2
3
4
3 2                           
1
1
10

Sample Output

1
10 2

HINT

两种砍的方法: (1)(1)(10)(1 1)(10)
n50000,0mmin(n1,1000),1Li1000n\leq 50000,0\leq m\leq \min(n-1,10 00),1\leq Li\leq 1000.

Solution

第一问贪心找出来。
第二问,对于每一个ii,找到最远的一个符合siskmxs_i-s_k\leq mx
fi,jf_{i,j}表示前jj个木棍分成ii个部分的方案数
fi,j=fi1,l(l[k,i1])f_{i,j}=\sum f_{i-1,l} (l\in [k,i-1])
复杂度是O(n2m)O(n^2m),前缀和优化后是O(nm)O(nm).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 51000;
int n, m;
int a[N], s[N], t;
bool check(int x) {
int res = 0, cnt = 1;
for(int i = 1; i <= n; ++i) {
if(res + a[i] > x) {
++cnt;
res = a[i];
} else res += a[i];
}
return cnt <= m;
}
int solve() {
int r = 50000000, l = t-1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid;
}
return r;
}
int pre[N];
int mx = 0;
int get(int val, int x) {
int l = -1, r = x;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(s[x] - s[mid] <= mx) r = mid;
else l = mid;
}
return r;
}
int f[2][N], g[N];
const int p = 10007;
int add(int &x, int v) {
x += v;
if(x >= p) x %= p;
}
int main() {
n = read(), m = read();
++m;
for(int i = 1; i <= n; ++i) a[i] = read(), s[i] = s[i - 1] + a[i], t = max(t, a[i]);
mx = solve();
for(int i = 1; i <= n; ++i)
pre[i] = get(s[i], i);
bool c = 0;
int ans = 0;
f[0][0] = 1;
for(int i = 1; i <= m;++i) {
c ^= 1;
g[0] = f[c ^ 1][0];
for(int j = 1; j <= n; ++j) g[j] = (g[j - 1] + f[c ^ 1][j]) % p;
memset(f[c], 0, sizeof f[c]);
for(int j = 1; j <= n; ++j) {
if(pre[j] == 0) f[c][j] = g[j - 1];
else f[c][j] = (g[j - 1] - g[pre[j] - 1] + p) %p;
}
add(ans, f[c][n]);
}
printf("%d %d\n", mx, ans);
return 0;
}