题解 P1281 【书的复制】

· · 题解

小弱c的题解，要写傻弱也能看懂的题解

看到题目秒想，马上想到一个熟（mo）悉（xing）的模型：将n个物品分k份的最优解；

第一反应想到了两题：

P1594 护卫队

p1018 乘积最大

第二反应，我只学过求最优的值，不管了，先打出来当复习。

【问题分析】

因为书是不能排序的，所以单调处理，DP死套路：

1、问什么设什么：

f[i][j]表示前 i 本书分给 j 个人，

2、做过5题以上DP的小弱都应该想到，需要第三重循环，我设 k 用来表示*最后一个人拿的第一本书的编号*

k枚举的范围就是（j->i）：因为前面最少要保留 j-1本书分给前面的 j-1个人，最后一个人自己最少也要有一本，所以右边边界就是 i

3、到这里已经可以把最优解（每人分到的书页的上限）求出来，然后就懵笔了。去翻题解，原来离成功只差一步贪心。从后往前（题目说要前面的人尽可能没那么累），把书扔给各个人就A了。

还有一些过程中的坑，代码里面告诉你。

4、忘了说，题解告诉我可以用二分来找最优值，果然我很弱，于是又打了一遍二分，发现自己二分超级不熟，有3个点搞了2个小时。

5、看了代码觉得我很丑，马上告诉我，我一定写到你能看懂为之！！！

ps：由于我很懒，只有dp和二分的两个函数我是分开打的，其他都是复制的，看不懂你打给我。

dp的代码：

    #include<cstdio>
    #include<cstring>
    int f[510][510];// f[i][j] 表示把 前 i本书 分给 k 个人 
    int ma[510],su[510];
    int n,m;
    int maxx(int x,int y) { return x>y?x:y; } 
    int minn(int x,int y) { return x<y?x:y; } 
    void ff()
    {
        for(int j=2;j<=m;j++)
        {
            for(int i=j;i<=n;i++)
            {
                for(int k=j;k<=i;k++)//k 为 最后一个人拿到的第一本书的编号 
                {
                    int an=0;
                    an=maxx(f[k-1][j-1],su[i]-su[k-1]);
                    f[i][j]=minn(f[i][j],an);
                }
            }
        }
    }
    void pr(int l,int r) //打印当前左右边界内的部分 
    {
        int ss=0;
        for(int i=r;i>=l;i--)
        {
            if(ss+ma[i]>f[n][m])
            {
                pr(l,i);
                printf("%d %d\n",i+1,r);//逆序输出，回溯时才打印 
                return ; 
            }
            ss+=ma[i];
        }
        printf("%d %d\n",1,r);//关于第一个人的特殊处理（边界） 
    }
    int main()
    {
        memset(su,0,sizeof(su));//预处理前 N 项和的数组 
        memset(f,63,sizeof(f));
        scanf("%d %d",&n,&m); if(n==0) return 0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&ma[i]); 
            su[i]=ma[i]+su[i-1];
            f[i][1]=su[i];
        }
        ff();
        //printf("%d\n",f[n][m]);
        pr(1,n);
        return 0;
    }

二分的代码：

    #include<cstdio>
    #include<cstring>
    int n,m,ans;
    int a[510];
    bool ch(int x)
    {
        int su=0,an=0;//an表示能分几个人 
        //printf("%d\n",x);
        for(int i=n;i>=1;i--)
        {
            if(i==1) an++; //最后一人（最前面的）需要特殊处理 
            if(su+a[i]<=x)
            {
                su+=a[i];
            }
            else
            {
                an++;su=a[i];
            }
        }
        if(an<=m) return 1;
        return 0;
    }
    void pr(int l,int r) //打印当前左右边界内的部分 
    {
        int ss=0;
        for(int i=r;i>=l;i--)
        {
            if(ss+a[i]>ans)
            {
                pr(l,i);
                printf("%d %d\n",i+1,r);//逆序输出，回溯时才打印 
                return ; 
            }
            ss+=a[i];
        }
        printf("%d %d\n",1,r);//关于第一个人的特殊处理（边界） 
    }
    int main()
    {
        scanf("%d %d",&n,&m); if(n==0) return 0;// 判 0 的坑点，我wa了3次 
        int l=0,r,mid;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            r+=a[i]; 
        }
        // 二分模板
        while(l<=r)
        {
            mid=(l+r)/2;
            if(ch(mid))
            {
                ans=mid; //ans存的就是每个人能分到的页数最大值，用这个来判输出 
                r=mid-1;
            }
            else l=mid+1;
        }
        //printf("%d\n",ans);
        pr(1,n);// 打印函数（我用递归来实现的，直接倒推打循环也是可以的） 
        return 0;
    }