BZOJ 1044: [HAOI2008]木棍分割(二分+dp)

Description

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

Input

  输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.

Output

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

Sample Input

3 2
1
1
10

Sample Output

10 2

HINT

两种砍的方法: (1)(1)(10)和(1 1)(10)

整个题看上去和某次cf的C很像。。。

第一问的话二分最大长度,贪心的判断是否可以保证在m段内凑完。

第二问肯定dp了。dp[i][j]代表前j个木棒组成了i段的方案数,,其中a[k+1]+….a[i]应该小于等于第一问求出来的答案。但这样的话是O(n^2*m)的时间复杂度,而且空间复杂度是O(n*m)也炸了。

其实空间优化的话,就是因为每次转移其实只和上一段的dp值有关滚动数组就可以了。

时间上的优化,因为发现每次求dp值的时候相当于求取一段区间和,想到之前玲珑杯用前缀和维护一下就可以了。然后其实随着j值的增加,k的最小值也是单调不递减的。。所以我们可以类似像单调队列那样维护这个最小的位置,统计上一轮答案的前缀。如果出现当前位置不符合的情况减去就可以了。

但是还是有些细节的。初始化dp[0][]其实代表的是形成1段的方案数。而且其中有取模中的减法,所以可能出现负数,需要处理好。。。

发现我写的常数特别大。。。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注