NKOJ 4244（HAOI 2008）木棍分割（算法与技巧：二分答案、动态规划、单调队列、前缀和优化及滚动数组）

P4244【HAOI2008】木棍分割

问题描述

共拥有n根木棒，在此过程中每根都有特定的长度参数Li。这些木棒依次连接在一起形成一个完整的序列，在这个序列中存在多个接合点。根据规定，在这些接合点中最多可以选择切开m个位置来进行切断操作。经过切割后，则这些木棒被分割成若干段。为了满足题目中的约束条件是使得最长的一段尽可能短，并在此基础上统计满足这一条件的不同切割方案的数量，并对计算结果取模10007。

输入格式

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

输出格式

两个数值中包含两个部分:第一个数值是指在总长度中最大段落的最小可能长度;第二个数值则是满足条件的不同切割方法的数量.

样例输入

3 2
1
1
10

样例输出

10 2

数据范围

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

---

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

接下来考虑到方案数量，并建立递归关系：定义 F[i][j] 为前 i 段切 j 刀且满足每一段长度不超过的切法总数。
不难看