BZOJ1044 [HAOI2008]木棍分割

题意

​   有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。。。

题解

第一问显然可以二分做。

第二问的话:

f[i,j]f[i,j]表示前i个,分成j段,其中第i个是第j段的结尾有多少情况
$f[i,j] = \sum{f[k][j-1]} ——满足k<i且sum[i] - sum[k-1] <= L $
两个指针扫一遍就可以了

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
namespace IO{
const int __buffsize = 1000000;char __buff[__buffsize];char *__buffS, *__buffT;
char getch(){if (__buffS == __buffT){__buffT = (__buffS = __buff) + fread(__buff,1,__buffsize,stdin);if (__buffS == __buffT) return EOF;}return *__buffS++;}
#define getch getchar
int read(){int T = 0,f = 1;char c = getch();while ((c<'0'||c>'9')&&c!='-') c=getch();if(c=='-')f=-1,c=getch();while (c>='0'&&c<='9'){T=((T<<1)+(T<<3))+c-48;c=getch();}return T*f;}
void write(int x){if(x < 0) putchar('0'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
};
#define pc putchar
using namespace IO;
int a[50005],n,m,L,R,res;
bool check(int mid){
int cnt=0,res=0;
for (int i=1;i<=n;i++){
if (cnt + a[i] > mid){
cnt = a[i];
res ++;
} else
cnt += a[i];
}
return res <= m;
}
int sum[50005];
int Ans;
const int Mod = 1e4+7;
int f[2][50005];
int main(){
n = read();m = read();
L = 0,R = 0;
sum[0]=0;
for (int i=1;i<=n;i++){
a[i] = read();
L=max(L,a[i]);
R+=a[i];
sum[i] = sum[i-1] + a[i];
}
while(L<R){
int mid = (L+R)>>1;
if(check(mid)) R=mid; else L=mid+1;
}
Ans = 0;
write(L);pc(' ');
for (int i=1;i<=n;i++) f[0][i] = (sum[i]<=L);
for (int j=1;j<=m;j++){
int tot=0,_=1;
for (int i=1;i<=n;i++){
while(_<i && sum[i]-sum[_]>L){
tot = (tot - f[(j-1)&1][_] + Mod)%Mod;
_++;
}
f[j&1][i] = tot;
tot = (tot + f[(j-1)&1][i]) % Mod;
}
Ans = (Ans + f[j&1][n]) % Mod;
}
write(Ans);pc('\n');
return 0;
}
文章目录
  1. 1. 题意
  2. 2. 题解