首页 > 代码库 > [HAOI2008]木棍分割
[HAOI2008]木棍分割
https://www.luogu.org/problem/show?pid=2511
题目描述
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果[b]mod 10007[/b]。。。
输入输出格式
输入格式：
输入文件第一行有2个数n,m. 接下来n行每行一个正整数Li,表示第i根木棍的长度.
输出格式：
输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.
输入输出样例
输入样例#1：
3 2 1 110
输出样例#1：
10 2
说明
两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.
第一问二分答案
第二问dp
dp[i][j] 表示前i根木棍，切了j刀的方案数
令ll[i] 表示第i根木棍向左最远能根第几根木棍连在一起
状态转移：dp[i][j] = Σ dp[k][j-1] k∈[ ll[i]，i ]
初始化：如果前i根木棍的和<二分的答案，dp[i][0]=1
ans=Σ dp[n][i] i∈[0,m]
时间复杂度 O（n^3），空间：O（n^2）
TLE && MLE
时间可以通过前缀和优化至O（n^2）
空间可以压去第二维优化至O（n）
未优化 TLE && MLE代码
#include<cstdio>#include<algorithm>#define mod 10007#define N 5001using namespace std;int n,m,ans;int a[N],sum[N];int l,r,mid,tmp;int ll[N],dp[N][N];bool check(){ if(a[1]>mid) return false; int now=a[1]; tmp=0; for(int i=1;i<n;i++) { if(now+a[i+1]>mid) { if(a[i+1]>mid) return false; if(tmp<m) tmp++; else return false; now=a[i+1]; } else now+=a[i+1]; } return true;}void solve1(){ r=sum[n]; while(l<=r) { mid=l+r>>1; if(check()) ans=mid,r=mid-1; else l=mid+1; } printf("%d ",ans); }void solve2(){ ll[1]=1; for(int i=2;i<=n;i++) for(int j=ll[i-1];j<=i;j++) if(sum[i]-sum[j-1]<=ans) { ll[i]=j; break; } for(int i=1;i<=n;i++) if(sum[i]<=ans) dp[i][0]=1; else break; for(int i=2;i<=n;i++) for(int j=1;j<=min(i-1,m);j++) for(int k=ll[i]-1;k<i;k++) dp[i][j]+=dp[k][j-1]; ans=0; for(int i=0;i<=m;i++) ans=(ans+dp[n][i])%mod; printf("%d",ans);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; solve1(); solve2();}
优化 后 AC代码
#include<cstdio>#include<algorithm>#define N 50001using namespace std;const int mod=10007;int n,m,ans;int a[N],sum[N];int l,r,mid,tmp;int ll[N],dp[N],f[N];bool check(){ if(a[1]>mid) return false; int now=a[1]; tmp=0; for(int i=1;i<n;i++) { if(now+a[i+1]>mid) { if(a[i+1]>mid) return false; if(tmp<m) tmp++; else return false; now=a[i+1]; } else now+=a[i+1]; } return true;}void solve1(){ r=sum[n]; while(l<=r) { mid=l+r>>1; if(check()) ans=mid,r=mid-1; else l=mid+1; } printf("%d ",ans); }void solve2(){ ll[1]=1; for(int i=2;i<=n;i++) for(int j=ll[i-1];j<=i;j++) if(sum[i]-sum[j-1]<=ans) { ll[i]=j; break; } for(int i=1;i<=n;i++) if(sum[i]<=ans) dp[i]=1; else break; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+dp[i]; ans=dp[n]; for(int j=1;j<=m;j++) { for(int i=1;i<=j;i++) dp[i]=0; for(int i=j+1;i<=n;i++) { if(ll[i]-2<=0) dp[i]=sum[i-1]; else dp[i]=(sum[i-1]-sum[ll[i]-2]+mod)%mod; } sum[0]=0; for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+dp[i])%mod; ans=(ans+dp[n])%mod; } printf("%d",ans);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; solve1(); solve2();}
[HAOI2008]木棍分割
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。