一个人的巴黎

用户名：uq_36478041918

访问量：15003

签　名：

等　　级
排　　名	105
经　　验	8305
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

编写题解 1132: 最大数问题数组通俗易懂
浏览：755

优秀的拆分,方法都会，注意细节即可，考察递归思想
浏览：361

奖学金，运用sort函数对结构体类型排序
浏览：283

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）指针写法！

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

复制书稿(动态规划 + 贪心)

　　作者: 一个人的巴黎　　　　发表时间：2022-02-14 15:14:24 浏览：440　|　评论：0　

原题链接：信息学奥赛一本通T1278- 复制书稿

本题可以使用动态规划解决，设f(i,j)为当前j本书交由i个人抄写，需要的最短时间，则动态转移方程为 f(i,j)=min(j=0...i){max(f[i-1][j],A[j]+A[j+1]+...+A[i])};

动态规划求出的仅仅是最优质，如果要输出具体方案，还需要根据动态规划计算的最优质，做一个贪心设计。具体来说，设最优质为T，那么k个人，每个人抄写最多T页。从最后后一本书开始按逆序将数分配给k个人去抄写，从第k个人开始，如果他还能写，就给他；

否则第k个人的工作分配完毕，开始分配第k-1个人的工作；以后再是k-2个、k-3个......直至第一个。一遍贪心后，具体的方案就出来了。

```cpp
#include<iostream>
#include<algorithm>
#include<stack>
#define MAX 0x3f3f3f
using namespace std;
int m,K;//m本书，K个人
int *A;
int f[501][501];//f[k][i]为k个人最少需要多少时间抄完前i本书
int print(int i,int j)//递归输出抄写方案
{
    int t,x;
    if(j==0)return 0;
    if(j==1)//第一个人抄写1到i本书
    {
        cout<<1<<" "<<i<<endl;
        return 0;
    }
    t=i;x=A[i];
    while(x+A[t-1]<=f[K][m])
        //从最后一本书按逆序分配第j个人抄写，只要能写，就给他
    {
        x+=A[t-1];
        t--;
    }
    print(t-1,j-1);
       //用递归过程给第j-1个人分配抄写方案，这是只有t-1本书了
    cout<<t<<" "<<i<<endl;
      //递归返回时输出，因为递归过程是最后1个人先分配抄书
}
int main()
{
    cin>>m>>K;
    A=new int[m+1];
    for(int i=1;i<=m;i++)
        cin>>A[i];
        
    if(K>m)  K=m;
    
    int i,j,k;
    f[0][0]=0;//0个人抄0本书需要的时间为0
    for(j=1;j<=m;j++)
        f[0][j]=MAX;//0个人抄书总是抄不完的
    
    int sum,maxtime;
    for(k=1;k<=K;k++){
        f[k][0]=0;//k个人，0本书，需要时间0
        for(i=1;i<=m;i++){
            f[k][i]=MAX;
            sum=0;
            for(j=i;j>=0;j--){
                maxtime=max(f[k-1][j],sum);//k-1个人抄前j本书(0...i)最多需要的时间，相当于把整体分成几个片段，分析出这种划分出的片段中所需要的时间最长的
                f[k][i]=min(f[k][i],maxtime);//维护一个“时间最长”的那个片段在所有划分中最短
                
                if(j>0)  sum+=A[j];
            }
        }
    }
    print(m,K);
    return 0;
}
```

0.0分

15 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）指针写法！

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

复制书稿(动态规划 + 贪心)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C++代码）

去掉双斜杠注释（C语言代码）

DNA （C++代码）

点我有惊喜！你懂得！

数列排序（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

【偶数求和】（C语言代码）

局部变量作函数返回值的问题

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）指针写法！

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

复制书稿(动态规划 + 贪心)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C++代码）

去掉双斜杠注释 （C语言代码）

DNA （C++代码）

点我有惊喜！你懂得！

数列排序 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

【偶数求和】 （C语言代码）

局部变量作函数返回值的问题

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

　　评论区

去掉双斜杠注释（C语言代码）

数列排序（C语言代码）

【偶数求和】（C语言代码）