首页 > 代码库 > 木棍分割[HAOI2008]
木棍分割[HAOI2008]
题目描述
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连
接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长
度最大的一段长度最小. 并将结果mod 10007。。。
输入
输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.
输出
输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.
样例输入
3 2
1
1
10
样例输出
10 2
提示
两种砍的方法: (1)(1)(10)和(1 1)(10)
题解
人生第一道二分答案成就感满满!二分答案,是指在最小值和最大值之间二分枚举答案,逐渐把答案缩小到一个值得出最优解。二分答案的题目设问常常是最大值最小、最小值最大,解的可能性应该是单调的(即某值不可行则答案只能比它大或只能比它小),需要能简单地验证答案正确与否,要注意的就是防止死循环(不过这道题好像没有这个问题)。对于木棍分割,如果这个值可行,最优解可能比它更小,以它为上界看一看有没有更小的解;如果这个值不可行,只能舍弃它和比它更小的解,以它+1为下界搜索答案。 int check(long long x) { temp=he=0; for(int i=1;i<=n;i++) { if(he+li[i]<=x) he+=li[i]; else { he=li[i]; temp++; if(temp>m) return 0; } } if(temp>m) return 0; return 1; } le=yd,jg=zd;(最小解是单段木块长度的最大值,最大解是所有木块长度之和) while(le<jg) { mid=(le+jg)>>1; if(check(mid)) jg=mid; else le=mid+1; } dp部分优化空间复杂度用滚动数组,优化时间复杂度用类似单调队列的思路,和Watching firework is fun大同小异,最后结果为f[i][n]之和。f[i][j]表示j段木块切i次的方案,f[i][j]为所有满足sum[i]-sum[k]<=jg的f[k][j-1]之和(1<=k<i)。f[i]只与f[i-1]有关,第一维只有0和1;sum是单调的,只要维护一个f[k][j-1]之和每次从后部加上新值,从头部减去不满足条件的k对应的值即可。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int sj=50010; int li[sj],mod=10007,yd; int la,no,head,n,m,mid,temp,tail; long long s[sj],f[2][sj],zd,jg,le,he,fas; int dbj(int x,int y) { return x>y?x:y; } int xbj(int x,int y) { return x<y?x:y; } void init() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&li[i]); s[i]=s[i-1]+li[i]; zd+=li[i]; yd=dbj(li[i],yd); } } void dp() { for(int i=1;i<=n;i++) { if(s[i]<=jg) f[0][i]=1; if(s[i]>jg) break; } fas=f[0][n]; for(int j=1;j<=m;j++) { head=0; tail=0; he=0; la=(j+1)%2; no=j%2; for(int i=1;i<=n;i++) { if(i<j) continue; for(int k=tail+1;k<i;k++) he+=f[la][k]; tail=i-1; while(s[i]-s[head]>jg) { he-=f[la][head]; head++; } f[no][i]=he; f[no][i]%=mod; } fas+=f[no][n]; fas%=mod; } } int check(long long x) { temp=he=0; for(int i=1;i<=n;i++) { if(he+li[i]<=x) he+=li[i]; else { he=li[i]; temp++; if(temp>m) return 0; } } if(temp>m) return 0; return 1; } int main() { init(); le=yd,jg=zd; while(le<jg) { mid=(le+jg)>>1; if(check(mid)) jg=mid; else le=mid+1; } printf("%lld\n",jg); dp(); printf("%lld",fas); //while(1); return 0; }
木棍分割[HAOI2008]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。