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[2][MAXN];
int ps[MAXN];

bool ok(int x)
{
        int nowl=0,tt=m;
        int i;
        for (i=1;i<=n;i++)
        {
                if (le[i]>x)return false;
                nowl+=le[i];
                if (nowl>x)
                {
                        nowl=le[i];
                        tt--;
                        if (tt==-1)return false;
                }
        }
        if (tt<=-1)return false;
        return true;
}
void deal(int &x,int y)
{
        x+=y;x%=VAL1;
}
int q[MAXN*2];
int main()
{
        freopen("input.txt","r",stdin);
        int i,j;
        scanf("%d%d",&n,&m);
        int sum=0;
        for (i=1;i<=n;i++)scanf("%d",le+i),sum+=le[i];
        for (i=1;i<=n;i++)ps[i]=ps[i-1]+le[i];
        ps[0]=le[0];
        int ans1,ans2=0;
        int l=1,r=sum,mid;
        while (l+1<r)
        {
                mid=(l+r)>>1;;
                if (ok(mid))
                {
                        r=mid;
                }else
                {
                        l=mid;
                }
        }
        ans1=r;
        int * a,*b;
        int ope,clo,res;
        f[0][0]=1;
        a=f[0];b=f[1];
        for (i=0;i<m;i++)
        {
                res=a[0];
                ope=0,clo=0;
                q[0]=0;
                for (j=1;j<=n;j++)
                {
                        while (ope<=clo&&ps[j]-ps[q[ope]]>ans1)
                        {
                                res-=a[ope++];
                                if(res<0)res+=VAL1;
                        }
                        b[j]=res;
                        res+=a[++clo];
                        q[clo]=j;
                        res%=VAL1;
                }
                for (j=n-1;j>=0;j--)//这里不是n，Wa了好久
                {
                        if (ps[n]-ps[j]>ans1)break;
                        ans2+=b[j];
                        ans2%=VAL1;
                }
                memset(a,0,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
",ans1,ans2);

}