BZOJ 1044 HAOI2008 木棍分割

1044: [HAOI2008]木棍分割

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4241  Solved: 1627
[Submit][Status][Discuss]
Description

　　有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连
接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长
度最大的一段长度最小. 并将结果mod 10007。。。

Input

　　输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.

Output

　　输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.

Sample Input
2                           


Sample Output
2
HINT

两种砍的方法: (1)(1)(10)和(1 1)(10)

第一问很显然二分+贪心
第二问也很显然是一个dp
但是裸的dp复杂度应该是n^2m的
f[i][j]表示枚举到i切了刀并且不超过最大长度的方案数
f[i][j]=sigmaf[k][j-1] (mink<k<i-1) mink表示k最小取到的数
那么sum[i]-sum[k]<=MAXNLEN
我们要考虑怎么省去一维n,我们想到前缀和是单调递增的
所以随着我们枚举i最小符合的前缀的下标也是单调递增的，我们可以去维护
f[mink]~f[i-1]的和sumf，如果mink不符合的话就减去，算完后再把f[i][j-1]
加到sumf中

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 inline int read(){
 4     int x=0;int f=1;char ch=getchar();
 5     while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
 6     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
 7     return x*f;
 8 }
 9 const int MAXN=1e6+10;
10 const int mod=10007;
11 int f[3][MAXN]={},n,m,a[MAXN],sum[MAXN];
12 inline bool check(int xx){
13     int sum=0;
14     int summ=0;
15     for(int i=1;i<=n;i++){
16         if(a[i]>xx) return 0;
17         sum+=a[i];
18         if(sum>xx){
19             sum=a[i];summ++;
20         }
21     }
22     return summ<=m;
23 }
24 inline int  erfen(){
25     int leftt=1;int rightt=100000017;
26     while(leftt+1<rightt){
27         int mid=(rightt+leftt)>>1;
28         if(check(mid)) rightt=mid;
29         else leftt=mid;
30     }
31     if(check(leftt)) return leftt;
32     else return rightt;
33 } 
34 void init(){
35     n=read();m=read();
36     for(int i=1;i<=n;i++){
37         a[i]=read();
38         sum[i]=sum[i-1]+a[i];
39     }
40 }
41 void dp(){
42     int k=erfen();
43     cout<<k<<' ';
44     int cnt=1;
45     int ans=0;
46     for(int i=0;i<=m;i++){
47         int sumf=0;int mink=0;//sumf表示f的总和 
48         for(int j=1;j<=n;j++){
49             if(i==0){
50                 if(sum[j]<=k) f[cnt][j]=1;
51                 else f[cnt][j]=0;
52             }
53             else{
54                 while(sum[j]-sum[mink]>k){
55                     sumf-=f[cnt^1][mink];
56                     sumf=(sumf+mod)%mod;
57                     mink++;
58                 }
59                 f[cnt][j]=sumf;
60                 f[cnt][j]%=mod;
61                 sumf+=f[cnt^1][j];
62                 sumf%=mod;
63             }
64         }
65         ans+=f[cnt][n];
66         ans%=mod;
67         cnt^=1;    
68     }
69     cout<<ans<<endl;
70 }
71 int main(){
72     //freopen("All.in","r",stdin);
73     //freopen("a.out","w",stdout);
74     init();
75     dp();
76     return 0;
77 }
78 
79 代码

代码