即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

书的复制

编程语言 qq_35914587 13℃ 0评论

QAQ


这道题是一道标准的DP题


设dp[i][j]为到i个人抄完第j本书所需要的最短时间


处理一个前缀和数组s,s[i]表示抄完第i本书所需的总共时间


容易得到dp[i][j]=min(dp[i][j],max(dp[i-1][l],d[j]-d[l]))


l是指第i-1个人抄的最后一本书,那么第i个人就会从l+1开始抄啦,由于复制时间为抄写最多页数的人所用的时间,所以里面的值取max


可是这道题目并不是要我们输出最短时间,而是方案


想一下,由于这个顺序是单调的,我们可以用二分答案来做


可是我这里用了递归来找方案233


想法是这样滴


我们从最后一个人递归,只要他抄书的总时间不超过最大值,就让他一直去承包前面的书,直到超了最优时间为止,再递归前一个人,这样找出的方案就能够满足题目要求的如果有多解,则尽可能让前面的人少抄写。


下面是代码

#include 
#include 
#include 
using namespace std;
int a[9999];
int s[9999];
int dp[999][999];
int m,k;
void print(int x,int i)//x书,i人 
{
    if(i==0) return;
    if(i==1) //第一个人一定从第一本开始抄
    {
        printf("1 %d\n",x);
        return;
    } 
    int book=x;
    int time=a[x];

    while(time+a[book-1]<=dp[k][m])//一直向前找
     book--,time+=a[book];

    print(book-1,i-1);//第一个先输出,所以先递归,再输出

    printf("%d %d\n",book,x);
}
int main()
{

    memset(dp,127,sizeof(dp));
    scanf("%d%d",&m,&k);

    for(int i=1;i<=m;i++)
     scanf("%d",a+i),s[i]=a[i]+s[i-1],dp[1][i]=s[i];

    for(int i=2;i<=k;i++)
     for(int j=1;j<=m;j++)
      for(int l=1;l<=j-1;l++)
       dp[i][j]=min(dp[i][j],max(dp[i-1][l],s[j]-s[l]));

     print(m,k);

     return 0;
}

转载请注明:CodingBlog » 书的复制

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情