解题思路
这个问题分为两个部分：
第一部分：求最大段长度的最小值（二分答案）
-
使用二分查找确定最小的最大段长度
-
对于每个候选值
mid，用贪心检查是否能分成最多m+1段（切m刀） -
检查时尽量把木棍合并，直到超过
mid就开新段
第二部分：求方案数（动态规划）
-
f[j]表示考虑前j根木棍，当前切割段的方案数 -
lef[i]表示以i结尾时，能够满足最大段长度≤ans的最左切割位置 -
使用前缀和优化DP转移，将O(n²)优化到O(nm)
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 10,inf = 0x3f3f3f3f; ll n,m,a[N]; ll L,R; ll s[N],f[N],lef[N],sum,mod = 10007;// 检查函数：判断是否能在最大段长度不超过mid的情况下分成不超过m+1段 bool check(ll mid){ll len = 0,cnt = 1; // len:当前段长度, cnt:段数计数(初始为1段)for(int i = 1; i <= n; i++){if(len + a[i] > mid){ // 如果当前段加上这根木棍会超过midcnt++; // 需要新开一段len = a[i]; // 新段从当前木棍开始 }else len += a[i]; // 否则继续累加到当前段 }// 判断段数是否不超过m+1(切m刀分成m+1段)if(cnt <= m + 1) return 1;else return 0; }int main() {cin >> n >> m;// 输入数据并初始化二分边界for(int i = 1; i <= n; i++) scanf("%lld",&a[i]),R += a[i],L = max(L,a[i]);ll ans;// 二分查找：找到最小的最大段长度while(L <= R){ll mid = (L + R) >> 1;if(check(mid)){ // 如果mid可行，尝试更小的值ans = mid;R = mid - 1;}else L = mid + 1; // 否则需要更大的值 }// 预处理：计算前缀和和lef数组int top = 0;for(int i = 1; i <= n; i++){a[i] += a[i - 1]; // 将a数组转为前缀和数组// 找到满足a[i]-a[top]<=ans的最小topwhile(a[i] - a[top] > ans) top++;lef[i] = top; // 记录位置i对应的最左可行切割点 }// DP计算方案数fill(s,s + 1 + n,1); // 初始化前缀和数组，s[0]=1表示空序列方案数为1// 注意：循环m+1次，因为可以切0刀到m刀(共m+1种情况)for(int i = 1; i <= m + 1; i++){// 计算f[j]: 前j根木棍，当前切割段的方案数for(int j = 1; j <= n; j++) f[j] = (s[j - 1] - s[lef[j] - 1]) % mod;// 更新前缀和数组s，用于下一轮DPs[0] = 0;for(int j = 1; j <= n; j++) s[j] = f[j] + s[j - 1];// 累加当前切割次数下，分割到第n根木棍的方案数sum = (f[n] + sum) % mod;}cout << ans << " " << sum << endl;return 0; }