BZOJ 1044

1044: [HAOI2008]木棍分割

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1393 Solved: 497
[Submit][Status]

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

两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.

前半部分为极水的二分，后半部分的DP优化很经典.用f[i][j]表示砍了i此到第j个末的方法种数，直接用一般的DP暴空间+时间，改为滚动数组后还是TLE。可以发现DP中后一层完全有前一层的一个连续区间决定的，且这些区间起点终点都是递增的。便可借此优化。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 #define MAXN 50010

 #define MAXM 1010

 #define VAL1 10007

 #define VAL2 1100

 int le[MAXN];

 int n,m;

 int f[][MAXN];

 int ps[MAXN];

 bool ok(int x)

 {

         int nowl=,tt=m;

         int i;

         for (i=;i<=n;i++)

         {

                 if (le[i]>x)return false;

                 nowl+=le[i];

                 if (nowl>x)

                 {

                         nowl=le[i];

                         tt--;

                         if (tt==-)return false;

                 }

         }

         if (tt<=-)return false;

         return true;

 }

 void deal(int &x,int y)

 {

         x+=y;x%=VAL1;

 }

 int q[MAXN*];

 int main()

 {

         freopen("input.txt","r",stdin);

         int i,j;

         scanf("%d%d",&n,&m);

         int sum=;

         for (i=;i<=n;i++)scanf("%d",le+i),sum+=le[i];

         for (i=;i<=n;i++)ps[i]=ps[i-]+le[i];

         ps[]=le[];

         int ans1,ans2=;

         int l=,r=sum,mid;

         while (l+<r)

         {

                 mid=(l+r)>>;;

                 if (ok(mid))

                 {

                         r=mid;

                 }else

                 {

                         l=mid;

                 }

         }

         ans1=r;

         int * a,*b;

         int ope,clo,res;

         f[][]=;

         a=f[];b=f[];

         for (i=;i<m;i++)

         {

                 res=a[];

                 ope=,clo=;

                 q[]=;

                 for (j=;j<=n;j++)

                 {

                         while (ope<=clo&&ps[j]-ps[q[ope]]>ans1)

                         {

                                 res-=a[ope++];

                                 if(res<)res+=VAL1;

                         }

                         b[j]=res;

                         res+=a[++clo];

                         q[clo]=j;

                         res%=VAL1;

                 }

                 for (j=n-;j>=;j--)//这里不是n，Wa了好久

                 {

                         if (ps[n]-ps[j]>ans1)break;

                         ans2+=b[j];

                         ans2%=VAL1;

                 }

                 memset(a,,sizeof(int)*MAXN);

                 swap(a,b);

         }

         /*

         f[0][0]=1;

         for (i=1;i<=n;i++)

         {

                 for (j=i;j>0;j--)

                 {

                         if (ps[i]-ps[j-1]>ans1)break;

                         for (k=0;k<m;k++)

                         {

                                 deal(f[i%VAL2][k+1],f[(j-1)%VAL2][k]);

                         }

                 }

         }

         for (i=n;i>=1;i--)

         {

                 if (ps[n]-ps[i]>ans1)break;

                 ans2=(ans2+f[i%VAL2][m])%VAL1;

         }*/

         printf("%d %d\n",ans1,ans2);

 }

巴特西