NKOJ 4244 （HAOI 2008） 木棍分割 （二分答案+DP+单调队列+前缀和优化+滚动数组）

发表于 |
字数统计: 743字 | 阅读时长 ≈ 4min

P4244【HAOI2008】木棍分割

问题描述

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

输入格式

第一行有2个数n,m. 接下来n行每行一个正整数Li,表示第i根木棍的长度.

输出格式

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

样例输入

3 2
1
1
10

样例输出

10 2

数据范围

n<=50000, 0<=m<=min(n-1,1000)
1<=Li<=1000

首先，总长度最大的一段的最小值，显然的二分答案，水过。同时令答案为$T$

然后，考虑方案数，考虑递推，令$F[i][j]$表示前$i$段切$j$刀，且使得每段长度不超过$T$的方案数。
容易得到$$F[i][j]=\sum_{Sum[i]-Sum[k] \leq T} F[k][j-1]$$
其中$Sum$表示长度的前缀和，那么时间复杂度$O(mn^2)$，空间复杂度$O(mn)$，显然过不了。

空间很容易用滚动数组解决，那么考虑优化时间，注意到$Sum$单调递增，那么我们可以用单调队列维护$k$，那么就可以$O(1)$的获取到$k$的最小值，然后需要将$F[k][j-1]$到$F[i-1][j-1]$累和，考虑用前缀和优化，那么观察可以发现，只需要优先枚举$j$，然后就可以实现前缀和优化了。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,p,q,A[50005],S[50005],SS[2][50005],F[2][50005],mod=10007,ans;
bool ok(int k)
{
	int i,tot=0,tmp=0;
	for(i=1;i<=n;i++)
	{
		tot+=A[i];
		if(tot>k)tot=A[i],tmp++;
	}
	if(tmp>m)return 0;
	return 1;
}
int EF(int l,int r)
{
	int mid;
	while(l<=r)
	{
		mid=l+r>>1;
		if(ok(mid))r=mid-1;
		else l=mid+1;
	}
	return l;
}
int main()
{
	int i,j,k,t=0,l,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&A[i]);
		t+=A[i];
		q=max(q,A[i]);
		S[i]=S[i-1]+A[i];
	}
	p=EF(q,t);
	for(i=1;i<=n;i++)
	{
		if(S[i]<=p)F[0][i]=1;
		SS[0][i]=SS[0][i-1]+F[0][i];
	}
	for(i=1;i<=m;i++)
	{
		l=i;x=i&1;y=x^1;
		for(j=i+1;j<=n;j++)
		{
			while(S[j]-S[l]>p)l++;
			F[x][j]=(SS[y][j-1]-SS[y][l-1])%mod;
			SS[x][j]=(SS[x][j-1]+F[x][j])%mod;
		}
		ans+=F[x][n];ans%=mod;
	}
	printf("%d %d",p,(ans+mod)%mod);
}