1044: [HAOI2008]木棒分割题解

1044: [HAOI2008]木棍分割题解

1044: [HAOI2008]木棍分割

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1235 Solved: 430
[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.

HINT

Source

第一问很水，直接二分答案+贪心验证即可

之后第二问略麻烦

用F[I][J]表示第I次砍在第J段上的方案数

其中第0段表示最左端，即没砍

我们可以得到F[I][J]=sigma(F[I-1][X])

即枚举前一刀

其中X必须合法，也就是说sum[x+1..j]<=第一问的ANS

这样的话效率是O(N^2M)，空间效率O(NM)

明显会痿掉

空间方面，我们可以用滚存降到O(N)

仔细想想，我们可以发现，F[I][J]=F[I][J-1]+F[I][J-2]+...F[I][X]

是一个区间和的形式

那么我们可以得到F[I][J]=SUM[F[I-1][X...J-1]]

那么我们可以用两个数组，一个是F[I][J]，意义如上

一个是K[I][J]，表示F[I][1..J]之和

那么我们就可以O(1)更新F[I][J]的值

一轮更新后暴力维护前缀和即可

时间复杂度O(NM)，空间复杂度N

下面贴代码

/**************************************************************
    Problem: 1044
    User: SKYDEC
    Language: C++
    Result: Accepted
    Time:2224 ms
    Memory:1604 kb
****************************************************************/
 
#include<stdio.h>
#include<cstring>
#define M 10007
using namespace std;
long n,m;long sum[51000];long f[51000];long g[51000];long k[51000];
bool can(long x)
{
     for(long i=1;i<=n;i++)if(sum[i]-sum[i-1]>x)return false;
     long lastp=0;long use=0;sum[n+1]=2100000000;
     for(long i=1;i<=n;i++)
     {
              if(sum[i]-sum[lastp]>x)
              {
                                     use++;
                                     lastp=i-1;
                                     }
                                     }
     if(lastp!=n)use++;
     return use<=m+1;
}
int main()
{
    scanf("%ld%ld",&n,&m);sum[0]=0;
    for(long i=1;i<=n;i++)
    {
             long v;scanf("%ld",&v);sum[i]=sum[i-1]+v;
             }
    long l,r;long ans=0;l=1;r=sum[n];
    while(l<r)
    {
              long mid=(l+r)>>1;
              if(can(mid)){ans=mid;r=mid;}else l=mid+1;
              }
    if(can(l))ans=l;
    printf("%ld ",ans);g[0]=0;long pos=0;
    for(long i=1;i<=n;i++)
    {
             while(sum[i]-sum[pos]>ans)pos++;
             g[i]=pos;
             }
    for(long i=1;i<=n;i++){f[i]=0;k[i]=1;}k[0]=1;f[0]=1;
    long cans=0;
    for(long c=1;c<=m+1;c++)
    {
             for(long p=1;p<=n;p++)
             {
                      f[p]=(k[p-1]-k[g[p]-1])%10007;
                      }
             k[0]=0;for(long i=1;i<=n;i++)k[i]=k[i-1]+f[i];
             //printf("%ld\n",f[n]);
             cans=(cans+f[n])%10007;
             }
    printf("%ld\n",cans);
    return 0;
}

5楼u013708304昨天 15:39: 太好了太神了！！！！！！！！！！！！

4楼u014037094昨天 15:35: 真心好

3楼u014037094昨天 15:35: 如同神一般！

2楼u014037094昨天 15:35: 太好了

1楼u014037094昨天 15:35: 太神了

1044: [HAOI2008]木棒分割 题解