题目描述

有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 dp[i - 1][k]$$,$$sum[k + 1] + sum[k + 2] + \cdots +sum[i] \le ans1$$

很显然转移的部分是连续的一段,并且随着i增大而后移...所以可以用单调队列维护一下

代码:

#include <algorithm>
#include <cstdio>
#include <cstring>

const int Maxv = 50010; 
const int Mod = 10007; 

int dp[2][Maxv], sum[Maxv], cnt, n, m; 

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

inline int read() {
    static int x, ch; 
    x = 0, ch = fgc(); 
    while (ch < '0' || ch > '9') ch = fgc(); 
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = fgc(); 
    return x; 
}

inline bool check(int x) {
    int cnt = 0, cur = 0; 

    for (int i = 1; i <= n; i++) {
        if (sum[i] > x) return false; 
        
        cur += sum[i]; 
        if (cur > x) {
            cur = sum[i]; 
            cnt++; 
        }
    }

    if (cur > 0) cnt++; 
    return cnt <= m; 
}

int ans1; 

int main() {
    n = read(); 
    m = read() + 1; 

    for (int i = 1; i <= n; i++) {
        sum[i] = read(); 
    }

    int l = 1, r = 1e9, mid;
    while (l <= r) {
        mid = (l + r) >> 1; 
        
        if (check(mid)) ans1 = mid, r = mid - 1; 
        else l = mid + 1; 
    }

    dp[0][0] = dp[1][0] = 1; 
    for (int i = 1; i <= n; i++) {  
        sum[i] += sum[i - 1]; 
    }

    int pre = 0, cur = 1; 
    for (int j = 1; j <= m; j++, pre = cur, cur ^= 1) {
        for (int i = 1, tot = 0, l = 1, r = 0; i <= n; i++) {
            tot = (tot + dp[pre][r++]) % Mod;
            
            while (l <= r && sum[r] - sum[l - 1] > ans1) {
                tot = (tot - dp[pre][l - 1] + Mod) % Mod; 
                l++; 
            }

            dp[cur][i] = tot; 
        }
    }

    printf("%d %d\n", ans1, dp[pre][n]); 
}