首页 > 代码库 > BZOJ 1044

BZOJ 1044

2024-07-04 19:32:18   228人阅读

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中后一层完全有前一层的一个连续区间决定的，且这些区间起点终点都是递增的。便可借此优化。

 

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 #define MAXN 50010
  7 #define MAXM 1010
  8 #define VAL1 10007
  9 #define VAL2 1100
 10 int le[MAXN];
 11 int n,m;
 12 int f[2][MAXN];
 13 int ps[MAXN];
 14 
 15 bool ok(int x)
 16 {
 17         int nowl=0,tt=m;
 18         int i;
 19         for (i=1;i<=n;i++)
 20         {
 21                 if (le[i]>x)return false;
 22                 nowl+=le[i];
 23                 if (nowl>x)
 24                 {
 25                         nowl=le[i];
 26                         tt--;
 27                         if (tt==-1)return false;
 28                 }
 29         }
 30         if (tt<=-1)return false;
 31         return true;
 32 }
 33 void deal(int &x,int y)
 34 {
 35         x+=y;x%=VAL1;
 36 }
 37 int q[MAXN*2];
 38 int main()
 39 {
 40         freopen("input.txt","r",stdin);
 41         int i,j;
 42         scanf("%d%d",&n,&m);
 43         int sum=0;
 44         for (i=1;i<=n;i++)scanf("%d",le+i),sum+=le[i];
 45         for (i=1;i<=n;i++)ps[i]=ps[i-1]+le[i];
 46         ps[0]=le[0];
 47         int ans1,ans2=0;
 48         int l=1,r=sum,mid;
 49         while (l+1<r)
 50         {
 51                 mid=(l+r)>>1;;
 52                 if (ok(mid))
 53                 {
 54                         r=mid;
 55                 }else
 56                 {
 57                         l=mid;
 58                 }
 59         }
 60         ans1=r;
 61         int * a,*b;
 62         int ope,clo,res;
 63         f[0][0]=1;
 64         a=f[0];b=f[1];
 65         for (i=0;i<m;i++)
 66         {
 67                 res=a[0];
 68                 ope=0,clo=0;
 69                 q[0]=0;
 70                 for (j=1;j<=n;j++)
 71                 {
 72                         while (ope<=clo&&ps[j]-ps[q[ope]]>ans1)
 73                         {
 74                                 res-=a[ope++];
 75                                 if(res<0)res+=VAL1;
 76                         }
 77                         b[j]=res;
 78                         res+=a[++clo];
 79                         q[clo]=j;
 80                         res%=VAL1;
 81                 }
 82                 for (j=n-1;j>=0;j--)//这里不是n，Wa了好久
 83                 {
 84                         if (ps[n]-ps[j]>ans1)break;
 85                         ans2+=b[j];
 86                         ans2%=VAL1;
 87                 }
 88                 memset(a,0,sizeof(int)*MAXN);
 89                 swap(a,b);
 90         }
 91 
 92         /*
 93         f[0][0]=1;
 94         for (i=1;i<=n;i++)
 95         {
 96                 for (j=i;j>0;j--)
 97                 {
 98                         if (ps[i]-ps[j-1]>ans1)break;
 99                         for (k=0;k<m;k++)
100                         {
101                                 deal(f[i%VAL2][k+1],f[(j-1)%VAL2][k]);
102                         }
103                 }
104         }
105         for (i=n;i>=1;i--)
106         {
107                 if (ps[n]-ps[i]>ans1)break;
108                 ans2=(ans2+f[i%VAL2][m])%VAL1;
109         }*/
110         printf("%d %d\n",ans1,ans2);
111 
112 }

 


联系
我们