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

3 2
1
1
10

Sample Output

10 2

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这个正确解。因此，裸的二分可行。

　　二分时有一些细节，比如可能会陷入死循环，对于这点，每个人的方法都不大一样，自己注意下。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int mod=10007;
 4 const int inf=1e9;
 5 int ans1,ans2;
 6 int N,M;
 7 int MAXX,MINN=inf;
 8 int L[50005];//记录原序列 
 9 int sum[50005];//原序列前缀和
10 void find(int,int);
11 bool jud(int);
12 int main(){
13     scanf("%d%d",&N,&M);
14     for(int i=1;i<=N;i++){
15         scanf("%d",&L[i]);
16         sum[i]=sum[i-1]+L[i];
17         MAXX=max(MAXX,L[i]);
18     }
19     find(MAXX,sum[N]);
20     
21     return 0;
22 }
23 void find(int l,int r){
24     if(r-l<=1){
25         if(r==l+1){
26             if(jud(l)==true){
27                 ans1=l;
28                 cout<<l<<endl;
29                 return ;
30             }
31             else{
32                 ans1=r;
33                 cout<<r<<endl;
34                 return ;
35             }
36         }
37         if(l==r){
38             ans1=l;
39             cout<<l<<endl;
40             return ;
41         }
42     }
43     int mid=(l+r)>>1;
44     if(jud(mid)==true){
45         find(l,mid);
46     }
47     else{
48         find(mid+1,r);
49     }
50 }
51 bool jud(int x){//当最长木棒为x时 
52     int tot=0;
53     int pos=0;
54     for(int i=1;i<=N-1;i++){//枚举每一条木棒，不用枚举最后一个，因为它后面本来就是断的 
55         if(sum[i]-sum[pos]<=x&&sum[i+1]-sum[pos]>x){
56             pos=i; 
57             tot++;
58         }
59     }
60     if(tot<=M)
61         return true;
62     else
63         return false;
64 }

　　第二问：在第一问的基础上求出情况个数，第一印象就是dp，暴力如下：

 1 int f[50005][1005];//f[i][j]表示前i个木棒，用j次切割，保证每一段都小于等于ans1的情况个数，f[i][j]=∑f[k][j-1] 
 2 for(int i=1;i<=N;i++){
 3     for(int j=1;j<=M;j++){
 4         for(int k=1;k<=i-1;k++){
 5             if(sum[i]-sum[k]<=ans1){
 6                 f[i][j]=(f[i][j]+f[k][j-1])%mod;
 7             }
 8         }
 9     }
10 }

　　呵呵了，时间空间都过不去,空间复杂度为 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) 。满足时间限制。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int mod=10007;
 4 const int inf=1e9;
 5 int ans1,ans2;
 6 int N,M;
 7 int Minf;
 8 int Sumf;
 9 int MAXX,MINN=inf;
10 int L[50005];
11 int sum[50005];
12 int f[50005][10];
13 void find(int,int);
14 bool jud(int);
15 int main(){
16     scanf("%d%d",&N,&M);
17     for(int i=1;i<=N;i++){
18         scanf("%d",&L[i]);
19         sum[i]=sum[i-1]+L[i];
20         MAXX=max(MAXX,L[i]);
21     }
22     find(MAXX,sum[N]);//二分
23 
24　　//-------DP-------------------------------------------
25     int Now=0,Last=1,Mink;
26     for(int i=0;i<=M;i++){
27         Sumf=0;
28         Mink=1;
29         for(int j=1;j<=N;j++){
30             if(i==0){
31                 if(sum[j]<=ans1)
32                     f[j][Now]=1;
33                 else
34                      f[j][Now]=0;
35             }
36             else{
37                 while(Mink<j&&sum[j]-sum[Mink]>ans1){
38                     Sumf-=f[Mink][Last];
39                     Sumf=(Sumf+mod)%mod;
40                     ++Mink;
41                 }
42                 f[j][Now]=Sumf;
43             }
44             Sumf+=f[j][Last];
45             Sumf%=mod;
46         }
47         ans2+=f[N][Now];
48         ans2%=mod;
49         Now^=1;
50            Last =Now^1;
51     }
52     printf("%d", ans2);
53     return 0;
54 }
55 void find(int l,int r){
56     if(r-l<=1){
57         if(r==l+1){
58             if(jud(l)==true){
59                 ans1=l;
60                 cout<<l<<" ";
61                 return ;
62             }
63             else{
64                 ans1=r;
65                 cout<<r<<" ";
66                 return ;
67             }
68         }
69         if(l==r){
70             ans1=l;
71             cout<<l<<" ";
72             return ;
73         }
74     }
75     int mid=(l+r)>>1;
76     if(jud(mid)==true){
77         find(l,mid);
78     }
79     else{
80         find(mid+1,r);
81     }
82 }
83 bool jud(int x){
84     int tot=0;
85     int pos=0;
86     for(int i=1;i<=N-1;i++){
87         if(sum[i]-sum[pos]<=x&&sum[i+1]-sum[pos]>x){
88             pos=i; 
89             tot++;
90         }
91     }
92     if(tot<=M)
93         return true;
94     else
95         return false;
96 }