P2511 [HAOI2008] 木棍分割

解题思路

这个问题分为两个部分：

第一部分：求最大段长度的最小值（二分答案）

• 使用二分查找确定最小的最大段长度

• 对于每个候选值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;
  }