题目地址：洛谷：【P2511】[HAOI2008]木棍分割 – 洛谷、BZOJ：Problem 1044. — [HAOI2008]木棍分割

题目描述

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

输入输出格式

输入格式：
输入文件第一行有2个数n,m. 接下来n行每行一个正整数Li,表示第i根木棍的长度.

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

输入输出样例

输入样例#1：

3 2                           
1 
1
10

输出样例#1：

10 2

说明

两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.

题解

第一问的答案可以二分答案得到，每次验证的时候贪心地让每一段尽量长，从而获得最小切割次数即可。
第二问需要用动态规划的想法，设计状态$dp[i][j]$为前$i$个木棍切成$j$段的方案数，转移为
$$ dp[i][j] = \sum_{1 \leq j < i, sum_i – sum_k \leq ans} dp[k][j-1] $$
然而我们这样开两维空间不可以，因此考虑把第二维滚动了。时间复杂度的问题，我们考虑转移的时候是对上一维区间求和，注意到区间的左端点是单调的，因此可以在外面维护一个可以转移的区间以及它们的和来做转移，将时间优化至$O(nm)$。
本题略有点卡常，减少取模次数即可。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 50005, MO = 10007;

int n, m, ans, ans2, a[MAXN], sum[MAXN], dp[MAXN][2];

inline bool check(int mid) {
    int sum = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] > mid) return false;
        sum += a[i];
        if(sum > mid) {
            cnt++; sum = a[i];
        }
    }
    return cnt <= m;
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint(); sum[i] = sum[i - 1] + a[i];
    }
    int l = 0, r = 1e9, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid; else l = mid;
    }
    ans = r;
    for(int i = 1; i <= n; i++) {
        if(sum[i] <= ans) dp[i][0] = 1; else break;
    }
    int now = 1;
    for(int j = 1; j <= m; j++) {
        int lsum = 0, ll = 1;
        for(int i = 1; i <= n; i++) {
            while(ll < i && sum[i] - sum[ll] > ans) {
                lsum -= dp[ll][now ^ 1]; lsum = (lsum + MO) % MO; ll++;
            }
            dp[i][now] = lsum;
            lsum = (lsum + dp[i][now ^ 1]) % MO;
        }
        ans2 = (ans2 + dp[n][now]) % MO;
        now ^= 1;
    }
    printf("%d %d", ans, ans2);
    return 0;
}