「BZOJ1044」[HAOI2008] 木棍分割
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
1
1
10
Sample Output
10 2
两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.
两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.
题解
第一问随便二分
dp加个类似队列。。。然后滚动数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<deque> #define mod 10007 #define inf 2000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans1,ans2; int a[50005],sum[50005]; int f[2][50005],q[50005]; bool jud(int x) { int tmp=0,sum=0; for(int i=1;i<=n;i++) { sum+=a[i]; if(sum>x){tmp++;sum=a[i];} if(tmp>m)return 0; if(a[i]>x)return 0; } return 1; } void solve1() { int l=1,r=sum[n]; while(l<=r) { int mid=(l+r)>>1; if(jud(mid)){ans1=mid;r=mid-1;} else l=mid+1; } } void solve2() { f[0][0]=1; int pre,cur,tot; for(int i=1;i<=m;i++) { pre=i&1;cur=pre^1; int l=1,r=1; q[1]=0;tot=f[cur][0]; for(int j=1;j<=n;j++) { while(l<=r&&sum[j]-sum[q[l]]>ans1) tot=(tot-f[cur][q[l++]]+mod)%mod; f[pre][j]=tot;q[++r]=j; tot=(tot+f[cur][j]+mod)%mod; } for(int j=n-1;j;j--) { if(sum[n]-sum[j]>ans1)break; ans2=(ans2+f[pre][j]+mod)%mod; } memset(f[cur],0,sizeof(f[cur])); } printf("%d\n",ans2); } int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; solve1(); printf("%d ",ans1); solve2(); return 0; } |
Subscribe
计数器 9787738
OI 课件=>
OI 课件=>