1044: [HAOI2008]木棍分割
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2161 Solved: 779
[Submit][Status][Discuss]
Description
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。。。
Input
输入文件第一行有2个数n,m. 接下来n行每行一个正整数Li,表示第i根木棍的长度.
Output
输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.
Sample Input
1
1
10
Sample Output
HINT
两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.
解析：
第一问：给定N个木棒，要求截[1,M]次，问在所有情况中最长的那个木棒的最小值是多少。再输出情况个数。
很显然，若 设截的次数为因变量x，截成之后的最长木棒的长度是y，(0<=x<=M；max(L[i])<y<∑L[i])可以看出 y随着x的上升而下降，是个单调函数(非严格单减)，所以我们可以二分答案，二分y的取值，判断若在此y下求的最少截的次数若小于M，则可行，继续二分，不行，也继续二分，知道精确到一个值即为所求(一般问最大中的最小或最小中的最大都是用二分答案来做的)。
二分答案还有一些容易晕的地方，比如这道题中，要求断开的是连接点，不是任意一处去断，可能会有疑问：如果仅仅是从[max,∑]之间二分，中间有很多数字是这些相邻木棒组不成的长度，有没有可能会算出这些数，导致WA呢？其实是不可能的，比如，假设二分枚举到的答案是X1，而真正答案是X2，且X2<X1,那么就说明有分M次，最大长度是X2，当确定X1可以是，我们的程序保证了继续二分，逼近X2这个正确解。因此，裸的二分可行。
二分时有一些细节，比如可能会陷入死循环，对于这点，每个人的方法都不大一样，自己注意下。
#include<bits/stdc++.h>
using namespace std;
const int mod=;
const int inf=1e9;
int ans1,ans2;
int N,M;
int MAXX,MINN=inf;
int L[];//记录原序列
int sum[];//原序列前缀和
void find(int,int);
bool jud(int);
int main(){
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++){
scanf("%d",&L[i]);
sum[i]=sum[i-]+L[i];
MAXX=max(MAXX,L[i]);
}
find(MAXX,sum[N]); return ;
}
void find(int l,int r){
if(r-l<=){
if(r==l+){
if(jud(l)==true){
ans1=l;
cout<<l<<endl;
return ;
}
else{
ans1=r;
cout<<r<<endl;
return ;
}
}
if(l==r){
ans1=l;
cout<<l<<endl;
return ;
}
}
int mid=(l+r)>>;
if(jud(mid)==true){
find(l,mid);
}
else{
find(mid+,r);
}
}
bool jud(int x){//当最长木棒为x时
int tot=;
int pos=;
for(int i=;i<=N-;i++){//枚举每一条木棒，不用枚举最后一个，因为它后面本来就是断的
if(sum[i]-sum[pos]<=x&&sum[i+]-sum[pos]>x){
pos=i;
tot++;
}
}
if(tot<=M)
return true;
else
return false;
}
第二问：在第一问的基础上求出情况个数，第一印象就是dp，暴力如下：
int f[][1005];//f[i][j]表示前i个木棒，用j次切割，保证每一段都小于等于ans1的情况个数，f[i][j]=∑f[k][j-1]
for(int i=;i<=N;i++){
for(int j=;j<=M;j++){
for(int k=;k<=i-;k++){
if(sum[i]-sum[k]<=ans1){
f[i][j]=(f[i][j]+f[k][j-])%mod;
}
}
}
}
呵呵了，时间空间都过不去,空间复杂度为 O(nm) ，时间复杂度为 O(n^2 m)。DP优化才是出题人最主要的目的。
首先先说空间上，由于状态转移方程为： f[i][j] = Σ f[k][j-1] ((1 <= k <= i-1) && (Sum[i] - Sum[k] <= ans1))，所以第二维空间 j 只和 j-1 有关，就用滚动数组滚动储存就好了，f[i][Now] 代替了 f[i][j] ， f[i][Now^1] 代替了 f[i][j-1] 。为了方便，我们把 f[][Now^1] 叫做 f[][Last] 。位运算异或1的目的是相互转化。这样空间复杂度为 O(n) 。满足空间限制。
然后是时间上的，考虑优化状态转移的过程。对于 f[i][Now] ，其实是 f[mink][Last]...f[i-1][Last] 这一段 f[k][Last] 的和，mink 是满足 Sum[i] - Sum[k] <= Len 的最小的 k ，那么，对于从 1 到 n 枚举的 i ，相对应的 mink 也一定是非递减的（因为 Sum[i] 是递增的）。我们记录下 f[1][Last]...f[i-1][Last] 的和 Sumf ，mink 初始设为 1，每次对于 i 将 mink 向后推移，推移的同时将被舍弃的 p 对应的 f[p][Last] 从 Sumf 中减去。那么 f[i][Now] 就是 Sumf 的值。这样时间复杂度为 O(nm) 。满足时间限制。
#include<bits/stdc++.h>
using namespace std;
const int mod=;
const int inf=1e9;
int ans1,ans2;
int N,M;
int Minf;
int Sumf;
int MAXX,MINN=inf;
int L[];
int sum[];
int f[][];
void find(int,int);
bool jud(int);
int main(){
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++){
scanf("%d",&L[i]);
sum[i]=sum[i-]+L[i];
MAXX=max(MAXX,L[i]);
}
find(MAXX,sum[N]);//二分 24 //-------DP-------------------------------------------
int Now=,Last=,Mink;
for(int i=;i<=M;i++){
Sumf=;
Mink=;
for(int j=;j<=N;j++){
if(i==){
if(sum[j]<=ans1)
f[j][Now]=;
else
f[j][Now]=;
}
else{
while(Mink<j&&sum[j]-sum[Mink]>ans1){
Sumf-=f[Mink][Last];
Sumf=(Sumf+mod)%mod;
++Mink;
}
f[j][Now]=Sumf;
}
Sumf+=f[j][Last];
Sumf%=mod;
}
ans2+=f[N][Now];
ans2%=mod;
Now^=;
Last =Now^;
}
printf("%d", ans2);
return ;
}
void find(int l,int r){
if(r-l<=){
if(r==l+){
if(jud(l)==true){
ans1=l;
cout<<l<<" ";
return ;
}
else{
ans1=r;
cout<<r<<" ";
return ;
}
}
if(l==r){
ans1=l;
cout<<l<<" ";
return ;
}
}
int mid=(l+r)>>;
if(jud(mid)==true){
find(l,mid);
}
else{
find(mid+,r);
}
}
bool jud(int x){
int tot=;
int pos=;
for(int i=;i<=N-;i++){
if(sum[i]-sum[pos]<=x&&sum[i+]-sum[pos]>x){
pos=i;
tot++;
}
}
if(tot<=M)
return true;
else
return false;
}