题解 SP43 【BOOKS1 - Copying Books】
本人对此题目的翻译： 【题目描述（大意）】 有m本书（每一本书都有一定的页数）和k台誊抄机器。一台机器只能够誊抄连续的若干本书，每本书只能由一台机器誊抄，每一台机器都必须有誊抄任务，誊抄机器可以同时工作。要求给出满足上述条件的工作分配方式，使得誊抄工作最早完成（即誊抄页数最多的机器誊抄页数最少）。 【输入格式】 第一行有一个正整数N，表示数据组数。 接下来有N组数据，第一行为两个整数m和k，接下来一行有m个整数p1~pm，第i个表示第i本书的页数。 【输出格式】 对于每组数据，输出工作分配方式，如果有多种工作分配方式，则输出机器誊抄页数字典序最靠前的那一种（这种分配方式要让誊抄靠前书本的机器分配到的页数尽量少）。 【数据范围】 N大约为200；1<=k<=m<=500；pi<=10,000,000。
这一道题最初想到了DP，设dp[i][j]表示第i本书被第(j+1)台机器誊抄的答案，sum[i]=p[1]+p[2]+...+p[i]，那么就有状态转移方程：dp[i][j]=min{dp[i'][j-1]+sum[i]-sum[i']|j-1<=i'<i}。 写出来测了一下，过了样例。然后就去写了一个暴力来对拍。 然而暴力写错了，于是就直接交了上去，得到了一个WA的结果。 后来把暴力调出来了。对拍时发现对于这种记录方案的题目，DP是不可行的。 然后就去吃饭了。吃饭的时候想到二分答案+贪心验证是可行的（而且效率还更高）。 饭后就把代码写了出来。对拍了一下，没有发现问题。 交了上去，得到了AC的结果。 想了想，如果只要输出最短时间或者删去“如果有多种工作分配方式，则输出机器誊抄页数字典序最靠前的那一种（这种分配方式要让誊抄靠前书本的机器分配到的页数尽量少）”并开spj，DP是可行的（DP只能够找到正确答案和一种解法，给出的那种解法一定程度上可以人为控制，但是我们无法做到保证它能够满足应输出解的要求）。 由对拍结果可知，该结论应该没有问题。
附件一：AC代码
#include<cstdio>
#include<cstring>
int T,n,m,p[510],l,r,mid,tot;
bool mark[510]; //记录该书是否为誊抄它的机器誊抄的最右边那本书
bool check(int x) //贪心验证
{
int used=0,sum=x;
for (int i=1;i<=n;i++)
{
if (p[i]>x) //如果有书的页数大于x就一定不行
return false;
if (sum+p[i]<=x) //如果这台机器能够在不大于x的时间内誊抄完这本书就贪心地让它来誊抄
sum+=p[i];
else //否则就要让下一台机器来誊抄
{
sum=p[i];
used++;
if (used>m) //如果当前所需机器数量最小值都大于机器总数也一定不行
return false;
}
}
return true; //通过了层层检查，可行
}
int main()
{
scanf("%d",&T);
while (T--)
{
tot=0; //多组数据时初始化不能忘记；tot表示所有书的总页数
memset(mark,false,sizeof mark);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",p+i),tot+=p[i]; //p+i相当于&p[i]
l=1,r=tot; //因为所有书本页数都为正数，所以下界为1；因为所有书本总页数为tot，所以上界为tot
while (l<r)
{
mid=l+r>>1;
if (check(mid)) //如果可行，范围缩小到[l,mid]
r=mid;
else //否则范围缩小到[mid+1,r]
l=mid+1;
}
printf("%d\n",l); //此时l=r，为可行的最短时间
int used=0,sum=l; //这里与check函数有类似之处
for (int i=n;i;i--) //“如果有多种工作分配方式，则输出机器誊抄页数字典序最靠前的那一种（这种分配方式要让誊抄靠前书本的机器分配到的页数尽量少）”，因此应该在可行范围内让靠后的机器誊抄尽量多的书本
if (sum+p[i]>l||m-used==i) //有可能不需要m台机器就可行，但是题目要求全部都要用上，因此把所有剩下的机器安排在前面
{
used++;
sum=p[i];
mark[i]=true; //记录为誊抄它的机器誊抄的最右边那本书
}
else
sum+=p[i];
for (int i=1;i<n;i++)
{
printf("%d ",p[i]);
if (mark[i]) //如果是誊抄它的机器誊抄的最右边那本书，则在后面输出分隔
printf("/ ");
}
printf("%d\n",p[n]); //最后一本后面不需要分隔；另外不知道SPOJ行末是否允许有空格
}
return 0;
}附件二：WA代码（这一份代码能够得出最短时间以及不一定符合输出要求的一种方案，有想知道DP方法怎么写的看这里）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,m,dp[510][510],sum[510],pre[510][510]; //pre[i][j]为最合适dp[i][j]的i'（之一）
bool mark[510]; //意义与AC代码相同
int main()
{
scanf("%d",&T);
while (T--)
{
memset(dp,0x2a,sizeof dp); //多组数据初始化
memset(mark,false,sizeof mark);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",sum+i);
sum[i]+=sum[i-1];
dp[i][0]=sum[i]; //预处理
}
for (int j=1;j<m;j++)
for (int i=1;i<=n;i++)
for (int ii=j-1;ii<i;ii++)
if (max(dp[ii][j-1],sum[i]-sum[ii])<dp[i][j]) //状态转移
dp[i][j]=max(dp[ii][j-1],sum[i]-sum[ii]),pre[i][j]=ii;
// printf("%d\n",dp[n][m]); //最短时间
for (int j=m-1,i=n;j;j--) //利用pre数组一个一个往前跳并记录
{
i=pre[i][j];
mark[i]=true;
}
for (int i=1;i<n;i++) //输出方式大致同AC代码
{
printf("%d ",sum[i]-sum[i-1]); //利用前缀和得到p[i]
if (mark[i])
printf("/ ");
}
printf("%d\n",sum[n]-sum[n-1]);
}
return 0;
}附件三：暴力代码（可以参考一下我对拍此类题目的暴力的写法）
#include<cstdio> //为了方便写，这里采用了状态压缩的方法，速度比较慢（用dfs虽然常数大且比较难写，但是更快），只能够过书本数<=11的数据，不过这种题小数据不会出错大数据也应该不会有错，因此我认为这样写暴力可行
#include<iostream>
using namespace std;
int tot[2000],t,n,m,a[510],ans,last,total,ansn; //last为上一台机器誊抄的最右边的那本书的位置；total为单个情况答案；ansn为答案的情况
int main()
{
for (int i=0;i<(1<<10);i++) //线性求一个数在二进制下“1”的个数，方法本人原创
tot[i]=tot[i>>1]+(i&1);
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",a+i);
a[i]+=a[i-1]; //前缀和
}
ans=0x7fffffff;
ansn=0;
for (int i=0;i<(1<<n-1);i++) //状压每本书是否为誊抄它的机器誊抄的最右边那本书；最后本书一定是一台机器誊抄的最右边那本书，所以只需要考虑前面的情况
if (tot[i]==m-1) //除最后一本书外共有(m-1)本书是一台机器誊抄的最右边那本书
{
total=0;
last=0;
for (int j=1;j<n;j++) //拆分该二进制数计算该情况的时间
if ((i>>j-1)&1)
total=max(a[j]-a[last],total),last=j;
total=max(total,a[n]-a[last]);
if (total<ans)
ans=total,ansn=i;
}
printf("%d\n",ans);
for (int i=1;i<n;i++)
{
printf("%d ",a[i]-a[i-1]); //除变量名，同DP代码
if ((ansn>>i-1)&1) //同样是拆分二进制数，以判断是否要输出间隔
printf("/ ");
}
printf("%d\n",a[n]-a[n-1]);
}
return 0;
}希望这篇题解对大家有帮助！