P2511 [HAOI2008]木棍分割 题解
无咕_
·
·
题解
题解索引
- 题目大意
- Solution
- AC code
- 类似题型
代码类型： C++（cpp）
是否吸氧：否
不压行代码长度：38
题目大意
题面：<传送门>
题意：有 n 条线段，给出 n 条线段的长度。线段初始是连接在一起的，现要求你切断 最多 m 处，要求求出：
-
切割后，总长度最大且长度值最短 的值对 10007 取模的结果。
-
输出 满足第一问 的方法数。
术语理解：前缀和优化dp。
Solution
第一次用紫题骗咕值，好鸡冻
声明：本题解中有一些部分确实借鉴了楼上楼下大佬们的部分内容，不过还是可以保证部分的原创性 因为我不会写sigma，更不知道多个sigma连在一起对不对，有错见谅 。
首先，我们可以看到这道题有一个特点：
切割时，只能切 原有的分段连接处。
我们按问题来吧，题目有两问，我们从第一问开始。
第一问：切割后，总长度最大且长度值最短的值对10007取模的结果
这个问题灰常简单，既然是找最合适的答案，无疑是 二分答案 最合适了。
做二分，首先确定数据所在的范围。第一问的答案范围无疑是 0 ~ (50000*1000) （这么点数据用模拟就行） 。
二分的基础思路就是假设，假设这个答案能行，代入进去算一遍看行不行。
我们假设的是最长长度，那么要求是首先不能有单一一段比他大的值，再一个就是分组的问题，分段的原则是 能少分就少分 。
最后分完段，再判断能不能分这么多段就行了。
第二问：输出满足第一问的方法数
其实说真的，楼上楼下的DALAO们都写了好多长串的公式，本人学问浅薄，不会写那些复杂的式子/fad。
n^3做法：黑 魔 法
按照楼上楼下大佬们写的 按照我们平常的思路，一般都会想到这个dp：
设 f[i][j] 表示前 i 根木棍分 j 组的方案数，
前提是 ```sum[i]-sum[k]<=ans1//ans1代表第一问的答案``` 。
其意义为枚举 $k$ 为分割点， $i$ 为木棍总数的枚举， $j$ 为分割点总数的枚举。
这里的 $m$ 是加了一的，因为割 $m$ 下分了 $m+1$ 段。
因其时间复杂度为 $O(n^3)$ 所以会 ~~学会黑魔法~~ T掉。
#### n*m做法：能 省 就 省
从上面的黑魔法我们了解到，靠三重循环是会T掉的。但当我们时间压到死之后又会发现， $f[50000][1000]$ 的数组是开不起的（我电脑太差还是）。
当然也可以用楼上楼下大佬的方法：用 ```short``` 建数组。
可我觉得这对数组不公平/dk
于是我写了一种只用一维数组去维护的方法。
首先，我们不论如何最终都是要求 $n$ 段分 $m+1$ 段，我们就可以直接压掉前面的那一维，没有必要了。
这样下来，都不需要滚动数组了。 ~~其实是我不会写~~
好的好的，正式开始讲了：
~~根据题目标签~~ 我们可以先建一个前缀和数组，用于存储前缀和，
```
sum[i]表示分成i组的方案总数的前缀和
```
然后写出dp数组，
```
f[i]表示分成i组的方案总数
```
根据一维前缀和数组的原理（此处是例子，不是此题答案），
```
sum[i]-sum[i-1]表示i的值
```
但我们如果原样套上的话，是错误的（因为他并不是 $i$ 的前缀和，而是分成 $i$ 组的方案总数的前缀和，所以我们应该将数组下标改成分成 $i$ 组的，即改成分成 $i$ 组的方案总数的起始点和结束点）。
于是为便于计算分成 $i$ 组的方案总数的起始点，又一个新数组诞生了：
```
zuo[i]表示i如果靠左分组i所能到达的最远结点
```
我们统计最靠左的结点时需要看具体值才能找出最合适的值，但求数组中一段的和最快最简便的还是前缀和数组，于是我们又有了一个数组：
```
for(int i=1;i<=n;i++){
a[i]+=a[i-1];//将a数组变成前缀和数组，因为a数组已经没用了（其实是我懒）
}
```
然后对于每个不同的 $i$ ，
```
while(a[i]-a[now]>ans1)now++;
zuo[i]=now;
```
这样就能找到合适的点了，那么我们计算分成 $i$ 组的方案总数就是：
```
sum[i]-sum[zuo[i]-1]
```
然后我们初始化数组，注意 $sun[i]$ 首先先全部为 $1$ （因为 $f[i]$ 还没算），$f[i]$ 初始化为 $0$ 。
接着是友善的dp方程，然后是更新前缀和，记录答案 ```ans2```
最后输出，这么愉快的结束了
当然还有一点我要讲，对于计算时的取模运算，一定要复制原题中的数字，不然很容易打错。 ~~要不是我因为10007写成了1007……这题解还能年轻一小时~~
## AC code
首先说下，具体的代码注释我都写在里面了。拒绝抄袭，从我做起（主要懂了就能写出来，没必要抄代码，不然还拿个棕名）
```cpp
#include<iostream>
#include<cstdio>
#define mods 10007
using namespace std;
const int MAX=5e5+9;
int n,m,a[MAX],ans1,ans2=0,sum[MAX],f[MAX],now=0,zuo[MAX];
bool check(int x){
/***********************
思路：假设x成立，那么开始分组，每次当前组的总长度加上当前枚举的长度超过了x时，就重新分一个组（尽量少分组），最后分完看看这些组成不成立
************************/
int len=0,num=1;//当前分组的总长度，当前总分的组数
for(int i=1;i<=n;i++){
if(a[i]>x)return false;//如果成立则x不成立
len+=a[i];//加入当前组
if(len>x)num++,len=a[i];//如果加入此组后大于了x，那么重新分一个组，并将a[i]作为新组的初始长度
}return num<=m;//看看这个最长是不是成立
}int main(){
scanf("%d%d",&n,&m);m++;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}int l=1,r=50000000;
while(l<=r){
int mid=(l+r)/2;
if(check(mid))ans1=mid,r=mid-1;
else l=mid+1;
}cout<<ans1<<" ";
for(int i=1;i<=n;i++){
//a数组后面没用处了所以直接霍霍就行
a[i]+=a[i-1];//将a数组变成前缀和数组
while(a[i]-a[now]>ans1)now++;//寻找最左点
zuo[i]=now;//记录最左结点
}for(int i=0;i<=n;i++)f[i]=0,sum[i]=1;//初始化
zuo[0]=1;//因为后面zuo[0]-1变成-1，越界了，所以变成1
for(int i=1;i<=m;i++){//段数（砍i-1段）
for(int j=1;j<=n;j++)f[j]=(sum[j-1]-sum[zuo[j]-1])%mods;//分成j块的分法总数等于j-1到zuo[j]的合理范围总数
if(i==1)sum[0]=0;////为了完善后一句，不让后一句出错
for(int j=1;j<=n;j++)sum[j]=f[j]+sum[j-1];//前缀和赋值（分成j块的分法总数的前缀和=分j块数的分法总数+分j-1块的前缀和）
ans2=(ans2+f[n])%mods;//更新答案（砍法+=分n块的总数）
}cout<<ans2<<endl;
return 0;
}
```
AC记录[<传送门>](https://www.luogu.com.cn/record/47413398)
## 类似题型
[P1043 [NOIP2003 普及组] 数字游戏](https://www.luogu.com.cn/problem/P1043)